【题目背景】

众所周知，刘备在长坂坡上与他的一众将领各种开挂，硬生生从曹操手中逃了出去，随后与孙权一起火烧赤壁、占有荆益、成就霸业。而曹操则在赤壁一败后再起不能，终生无力南下。

建安二十五年(220年)，曹操已到风烛残年，但仍难忘当年长坂的失误，霸业的破灭。他想如果在刘备逃亡的路中事先布下一些陷阱，便能拖延刘备的逃脱时间了。你作为曹操身边的太傅，有幸穿越到了208年的长坂坡，为大魏帝国贡献一份力，布置一些陷阱。但时空守卫者告诉你你不能改变历史，不能拖增大刘备的最大逃脱时间，但你身为魏武之仕，忠心报国，希望能添加一些陷阱使得刘备不论怎么逃跑所用的时间都一样。

 

【问题描述】

已知共有n个据点，n-1条栈道，保证据点联通。1号据点为刘备军逃跑的起点，当刘备军跑到某个据点后不能再前进时视为刘备军逃跑结束。在任意一个栈道上放置1个陷阱会使通过它的时间+1，且你可以在任意一个栈道上放置任意数量的陷阱。

现在问你在不改变刘备军当前最大逃跑时间的前提下，需要添加最少陷阱，使得刘备军的所有逃脱时间都尽量的大。

其实就是让你调整一些树边的边权，使得根到每个叶子结点的路径一样长

我们令d[i]为i到根的距离，mg[i]为i的子树中d的最大值，那么显然可以用一次dfs求出，让后做一次dp即可：我们每次将点x的权值加上mg[1]-mg[x]-k，让后递归下去，这相当于一个贪心的过程

#include
    
     #include
     
      #include
      
       #define N 500010using namespace std;struct Edge{ int v,c,nt; } G[N<<1];int h[N],f[N],sz[N],n,m,cnt=0,R; long long A=0,mg[N],d[N];inline void adj(int x,int y,int c){ G[++cnt]=(Edge){y,c,h[x]}; h[x]=cnt; }void dfs(int x,int p){	f[x]=p; sz[x]=1; mg[x]=d[x];	for(int v,i=h[x];i;i=G[i].nt)		if((v=G[i].v)!=p) {			d[v]=d[x]+G[i].c;			dfs(v,x); sz[x]+=sz[v];			mg[x]=max(mg[x],mg[v]);		}}void dp(int x,int k){	A+=(R-mg[x])-k;	for(int v,i=h[x];i;i=G[i].nt)		if((v=G[i].v)!=f[x]) dp(v,(R-mg[x]));}int main(){	scanf("%d",&n);	for(int x,y,c,i=1;i
      
     
    

结果我们发现可以优化，其实答案就是Σmg[f[i]]-mg[i]

#include
    
     #include
     
      #include
      
       #define N 500010using namespace std;struct Edge{ int v,c,nt; } G[N<<1];int h[N],f[N],sz[N],n,m,cnt=0,R; long long A=0,mg[N],d[N];inline void adj(int x,int y,int c){ G[++cnt]=(Edge){y,c,h[x]}; h[x]=cnt; }void dfs(int x,int p){	f[x]=p; sz[x]=1; mg[x]=d[x];	for(int v,i=h[x];i;i=G[i].nt)		if((v=G[i].v)!=p) {			d[v]=d[x]+G[i].c;			dfs(v,x); sz[x]+=sz[v];			mg[x]=max(mg[x],mg[v]);		}}int main(){	scanf("%d",&n);	for(int x,y,c,i=1;i