[ZJOI2007]时态同步 题解

题面

这道题是一道比较水的XXOI题；

我们可以发现，反着思考题目就变为了让所有叶子节点同时发出信号，然后这些信号同时到达根节点；

可以证明，这样答案不会改变；

那么我们可以自下而上dfs(),设f[u]表示以u为根，可以到达的最远距离；

那么很显然，对于点u，它对答案的贡献度就是num(它子节点的个数)*f[u]-sum(f[v]);

实现也比较容易，但要注意开long long;

#include <bits/stdc++.h>

#define inc(i,a,b) for(register int i=a;i<=b;i++)

#define LL long long

using namespace std;

int n,s;

struct littlestar{

    int to;

    int nxt;

    LL w;

}star[2000010];

int head[2000010],cnt;

void add(int u,int v,LL w)

{

    star[++cnt].to=v;

    star[cnt].nxt=head[u];

    head[u]=cnt;

    star[cnt].w=w;

}

LL f[1000010],ans;

void dfs(int u,int fa)

{

    LL sum=0;

    int num=0;

    for(int i=head[u];i;i=star[i].nxt){

        int v=star[i].to;

        if(v==fa) continue;

        dfs(v,u);

        ++num;

        f[u]=max(f[u],f[v]+star[i].w);

        sum+=f[v]+star[i].w;

    }

    ans+=(f[u]*num-sum);

}

int main()

{

    cin>>n>>s;

    inc(i,1,n-1){

        int u,v;

        LL w;

        scanf("%d%d%lld",&u,&v,&w);

        add(u,v,w);

        add(v,u,w);

    }

    dfs(s,0);

    cout<<ans;

}