每个边的实际花费费用为道路的权乘以道路两端的国家个数之差的绝对值，那么如果我们预处理每个点的子树的大小siz
通过树的遍历来遍历每一条边，因为是从我们求siz时使用的根出发，那么对于u->v的一条边，v的那一头的国家数量就是siz[v],而u的那一头的国家数量就是n-siz[v]
我们将两个数相减取绝对值abs(siz[v]-n+siz[v])，再乘以边权，就是每个边的实际花费费用
注意：不开long long 似乎要WA
总体实现如下：
#include <algorithm> #include <iostream> #include <cmath> #include <cstring> #include <map> #include <string> #include <vector> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> using namespace std; inline int read() { register int p(1),a(0);register char ch=getchar(); while((ch<‘0‘||ch>‘9‘)&&ch!=‘-‘) ch=getchar(); if(ch==‘-‘) p=-1,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) a=a*10+ch-48,ch=getchar(); return a*p; } const int N=1000100; int n,u,v,w,siz[N],head[N],cnt=0; long long ans=0; struct EDGE{int nxt,val,to;}e[N<<1]; void add(int u,int v,int w){e[++cnt]=(EDGE){head[u],w,v};head[u]=cnt;} void dfs(int u,int fa) { siz[u]=1; for(int i=head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to) if(fa!=v) { dfs(v,u); siz[u]+=siz[v]; } } void dfs2(int u,int fa) { for(int i=head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to) if(fa!=v) { ans+=(abs(siz[v]-n+siz[v])*1ll*e[i].val); dfs2(v,u); } } int main() { // freopen("input","r",stdin); // freopen("output","w",stdout); n=read(); for(int i=1;i<n;i++) { u=read(),v=read(),w=read(); add(u,v,w);add(v,u,w); } dfs(1,-1); dfs2(1,-1); printf("%lld",ans); return 0; }
原文：https://www.cnblogs.com/cold-cold/p/10029766.html