BZOJ 1060 [ZJOI2007]时态同步

题目大意

请你用最小次数进行操作（使得某一条边边权+1），使得一颗有根树的根到所有叶子节点的距离相等。

这道题一看到这么蛇皮根本无从下手那么不是DP就是贪心qwq

首先对于整个操作，肯定不会出现最终得到的相等的距离比现有的最长的距离大。对于每一次操作而言，它覆盖的边的深度越小，那么它的影响越大。所以贪心策略就是尽量往上放。

直接找到子树中最大的距离（设为$F_i$）对于每个儿子所在子树只要暴力把不是最长的抻到最长的就可以了。

注意使用long long.

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxN 500010
int n,s,inx,iny,inz,to[maxN<<1],nex[maxN<<1],val[maxN<<1],head[maxN],tot;
long long ans,f[maxN];
void addedge(int tx,int ty,int tz) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;}
void dfs(int pos,int pre)
{
    for(int i=head[pos];i;i=nex[i])
        if(to[i]!=pre)
        {
            dfs(to[i],pos);
            f[pos]=max(f[pos],f[to[i]]+val[i]);
        }
    for(int i=head[pos];i;i=nex[i])
        if(to[i]!=pre)
            ans+=f[pos]-f[to[i]]-val[i];
    return;
}
int main()
{
    scanf("%d%d",&n,&s);
    for(int i=1;i<n;++i) scanf("%d%d%d",&inx,&iny,&inz),addedge(inx,iny,inz),addedge(iny,inx,inz);
    dfs(s,0);
    printf("%lld\n",ans);
}