0分,只过了Subtask 0的第一个测试点,跪求大佬帮忙找到错误orz
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
#define int long long
vector<int> g[N];
int fa[N][18],depth[N];
int arr[N],cost1[N],cost2[N];
int diff[N],org[N];
queue<int> q;
int vis[N];
void bfs(int root){
memset(depth,0x3f,sizeof depth);
depth[0]=0;
depth[root]=1;
q.push(root);
while(q.size()){
int tmp = q.front();
q.pop();
for(auto x:g[tmp]){
if(depth[x]>depth[tmp]+1){
// cout<<"________________"<<endl;
q.push(x);// 别忘入队
depth[x] = depth[tmp]+1;
fa[x][0]=tmp;
for(int i=1;i<=17;++i){
fa[x][i]=fa[fa[x][i-1]][i-1];
}
}
}
}
}
int lca(int a,int b){
if(depth[a]<depth[b]) swap(a,b);
for(int i=17;i>=0;--i){
if(depth[fa[a][i]]>=depth[b]) a = fa[a][i];//注意等号
}
if(a==b) return a;
for(int i=17;i>=0;--i){
if(fa[a][i]!=fa[b][i]){
a = fa[a][i];
b =fa[b][i];
}
}
return fa[a][0];
}
void dfs(int u){
org[u]=diff[u];
for(auto x:g[u]){
if(x==fa[u][0]) continue;
dfs(x);//递归别忘dfs
org[u]+=diff[x];
}
return ;
}
signed main(){
// cout<<log2(N)<<endl;17.6097 0-17
int n,a,b,c1,c2,root;
scanf("%lld",&n);
// vis[1]=1;// 这里有问题
for(int i=1;i<n;++i){
scanf("%lld%lld%lld%lld",&a,&b,&c1,&c2);
g[a].push_back(b);
g[b].push_back(a);
if(i==1){
root=b;
vis[b]=1;
}
if(vis[a]) swap(a,b);
cost1[a] = c1;
cost2[a] = c2;
vis[a]=1;
// 这里不太对,对
// if(a>b) swap(a,b);
// cost1[b] = c1;
// cost2[b] = c2;
}
bfs(root);
for(int i=2;i<=n;++i){
// cout<<i<<" lca"<<lca(1,i)<<endl;
//边权差分
diff[i-1]++;// 注意审题
diff[i]++;
diff[lca(i-1,i)]-=2;
}
dfs(root);
int ans = 0;
for(int i=1;i<=n;++i){
if(i==root) continue;
if(cost1[i]*org[i]<cost2[i]) ans +=cost1[i]*org[i];
else ans += cost2[i];
}
cout<<ans<<endl;
return 0;
}