做这个题还是比较顺手的，起码做起来挺舒服的。他让我们求使所有叶子节点到根节点距离一样的代价，那么作为一颗子树来说首先就要满足这点，因为再往上走的路径都是一样的，因此我们需要先求所有子树的最大深度，然后答案=（子树最大深度-子树蛾子子树最大深度-子树到其蛾子的距离+修改蛾子子树的代价）
#include<iostream> #include<cstring> #include<cstdio> using namespace std; long long dp[500050],shu[500050]; int n,roo,tail,x,y,z,head[500050]; struct in { int to,ne,co; }ter[1000010]; inline void build(int f,int l,int c) { ter[++tail]=(in){l,head[f],c},head[f]=tail; ter[++tail]=(in){f,head[l],c},head[l]=tail; } void dfs(int ro,int fa) { if(head[ro]==-1)//如果发现当前这个点没有蛾子，说明这是叶子节点，返回 return; for(int i=head[ro];i!=-1;i=ter[i].ne) { int t=ter[i].to; if(t==fa) continue; dfs(t,ro); shu[ro]=max(shu[ro],shu[t]+ter[i].co);//先求出最大深度 } for(int i=head[ro];i!=-1;i=ter[i].ne) { int t=ter[i].to; if(t==fa) continue; dp[ro]+=shu[ro]-shu[t]-ter[i].co+dp[t];//答案取决于深度差于修改值之和 } } int main() { scanf("%d%d",&n,&roo); memset(head,-1,sizeof(head)); for(int i=1;i<=n-1;i++) scanf("%d%d%d",&x,&y,&z),build(x,y,z);//建图 dfs(roo,0); printf("%lld",dp[roo]); }
原文：http://www.cnblogs.com/Loi-dfkdsmbd/p/7725430.html