这边建议把两份代码都发出来,
方便大佬们看
by Glassy_Sky @ 2023-05-15 18:36:55
@[北射天狼](/user/289056) 你的cal函数没有递归
```cpp
#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;
cal(v,u);//新加的
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;
}
```
by liaiyang @ 2023-05-15 19:45:05
@[liaiyang](/user/783170) 对不起我脑子瞎了 + 眼睛抽了。
by 北射天狼 @ 2023-05-16 17:23:32