bzoj 1060 [ZJOI2007]时态同步（树形DP）

【题目链接】

http://www.lydsy.com/JudgeOnline/problem.php?id=1060

【题意】

求最少的增加量，使得以rt为根的树中由一个结点出发的所有到叶子结点的路长相等。

【思路】

树形DP。

设f[u]为以u为根的子树中到叶子的最大路长，只要把其他的所有路长都增加到f[u]就可以了。

【代码】

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 const int N = 5e5+10;
 8 
 9 struct Edge {
10     int v,w,nxt;
11 }e[N<<1];
12 int en=1,front[N];
13 void adde(int u,int v,int w) 
14 {
15     en++; e[en].v=v,e[en].w=w,e[en].nxt=front[u],front[u]=en;
16 }
17 
18 int n,rt;
19 int f[N]; ll ans;
20 
21 ll read()
22 {
23     char c=getchar(); ll f=1,x=0;
24     while(!isdigit(c)) {if(c=='-')f=-1; c=getchar();}
25     while(isdigit(c)) x=x*10+c-'0',c=getchar();
26     return x*f;
27 }
28 
29 void dfs(int u,int fa) {
30     for(int i=front[u];i;i=e[i].nxt) {
31         int v=e[i].v;
32         if(v!=fa) {
33             dfs(v,u);
34             f[u]=max(f[u],f[v]+e[i].w);
35         }
36     }
37     for(int i=front[u];i;i=e[i].nxt)
38         if(e[i].v!=fa) ans+=f[u]-f[e[i].v]-e[i].w;
39 }
40 
41 int main()
42 {
43     n=read(),rt=read();
44     for(int i=0;i<n-1;i++) {
45         int u=read(),v=read(),w=read();
46         adde(u,v,w),adde(v,u,w);
47     }
48     dfs(rt,-1);
49     printf("%lld
",ans);
50     return 0;
51 }

合影留念 :)