P1131 [ZJOI2007] 时态同步

Portal.

先找出树上以 $S$ 为起点最长的一条链，然后让其他链的长度都和该链对齐即可。

维护每个结点 $x$ 的子树最长链 $d_{\max }(x)$，则每次 DFS 求出最长链之后调整对齐的代价为 $d_{\max }(x)-(d_{\max }(so{n}_x)+w_i)$。

#include 
using namespace std;
#define int long long

const int maxn=5e5+5;
int head[maxn],V,cnt,mxd[maxn];
struct edge{int to,nxt,w;}e[maxn];

void add(int x,int y,int z){e[++cnt]=(edge){y,head[x],z},head[x]=cnt;}

void dfs(int x,int fa)
{
    for(int i=head[x];i;i=e[i].nxt)
    {
        if(e[i].to==fa) continue;
        dfs(e[i].to,x),mxd[x]=max(mxd[x],mxd[e[i].to]+e[i].w);
    }
    for(int i=head[x];i;i=e[i].nxt)
    {
        if(e[i].to==fa) continue;
        V+=mxd[x]-(mxd[e[i].to]+e[i].w);
    }
}

signed main()
{
    int N,S;cin>>N>>S;
    for(int i=1,a,b,t;i<N;i++) cin>>a>>b>>t,add(a,b,t),add(b,a,t);
    dfs(S,0);
    cout<<V;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32