有点不理解为什么把 cal 和 dfs 合并起来能AC(如注释),但是分开写的时候就错呢?
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll n;
ll size[N];
ll head[N],cnt = 0;
struct node{
int v,next,w;
}tree[N<<1];
ll ans = 0;
void add(int u,int v,int w)
{
tree[++cnt].next = head[u];
tree[cnt].v = v;
tree[cnt].w = w;
head[u] = cnt;
}
void dfs(int u,int father)
{
for (int i=head[u];i;i=tree[i].next){
int v = tree[i].v;
if (v == father)
continue;
dfs(v,u);
size[u] += size[v];
//ans += (ll)abs(size[v]*2 - n) * tree[i].w;
}
size[u]++;
}
void cal(int u,int father)
{
for (int i=head[u];i;i=tree[i].next){
int v = tree[i].v;
if (v == father)
continue;
long long sum = abs(n - size[v] - size[v]);
ans += (long long)tree[i].w * sum;
}
}
signed main()
{
scanf("%d",&n);
for (int i=1,u,v,w;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
dfs(1,-1);
cal(1,-1);
printf("%lld\n",ans);
return 0;
}