[BZOJ 1060] 时态同步

Link:

BZOJ 1060 传送门

Solution:

直接上树形$dp$统计当前节点到叶子的最长距离

在返回前统计答案，这样就保证每棵子树已经平衡，相当于只调整$w(i,son[i])$

可以发现每条边对答案的贡献为$dp[i]-dp[son[i]]-w(i,son[i])$

Code:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN=5e5+10,INF=1<<27;
int x,y,w,n,S,tot,dp[MAXN],head[MAXN];ll res=0;
struct edge{int to,nxt,w;}e[MAXN<<1];
void add(int from,int to,int w)
{e[++tot].nxt=head[from];e[tot].to=to;e[tot].w=w;head[from]=tot;}

void dfs(int x,int anc)
{
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=anc)
            dfs(e[i].to,x),dp[x]=max(dp[x],dp[e[i].to]+e[i].w);
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=anc) 
            res+=(dp[x]-dp[e[i].to]-e[i].w);
}

int main()
{
    scanf("%d%d",&n,&S);
    for(int i=1;i<n;i++)
        scanf("%d%d%d",&x,&y,&w),add(x,y,w),add(y,x,w);
    dfs(S,0);
    printf("%lld",res);
    return 0;
}