[ZJOJ2007]时态同步贪心

不是很懂为什么luogu标签是树形DP，感觉我想的就是一个贪心啊。。。

随机造几组数据，我们发现贪心的确可以得到最优解，那么为什么呢？

假设将所有时态贪心的调整是对的，
那么如果一个节点的各个儿子时态不同，那么强行统一，
为什么可以假设是对的？
因为观察到在一个点的上方+1，对它的子树的相对关系的没有影响的，
因此子树里面的时态同步只能在内部做，所以一步一步统一上来,
而且由于如果是要改变两个子树之间的大小关系的话，
因为是整个子树的修改，同时不影响到其他子树，因此这个时候就是在一个点的上方+1了，
同时因为每次只考虑子树内部的关系，所以整个子树的修改会被延后到上一个节点，
这时两个子树之间的修改就变成了子树内部的修改，因此递归上去即可

注意：由于f[x]中存的子树个数在不断增加，因此f[x]中的个数可能不只一个，因此如果要把f[x]中的子树增加到f[now]代表的子树的话，

因为路径不同，因此要修改cnt(f[x]中的子树个数)条路径，并且每条路径都是+相同的数，所以代价要*cnt

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 /*假设将所有时态贪心的调整是对的，
 4 那么如果一个节点的各个儿子时态不同，那么强行统一，
 5 为什么可以假设是对的？
 6 因为观察到在一个点的上方+1，对它的子树的相对关系的没有影响的，
 7 因此子树里面的时态同步只能在内部做，所以一步一步统一上来,
 8 而且由于如果是要改变两个子树之间的大小关系的话，
 9 因为是整个子树的修改，同时不影响到其他子树，因此这个时候就是在一个点的上方+1了，
10 同时因为每次只考虑子树内部的关系，所以整个子树的修改会被延后到上一个节点，
11 这时两个子树之间的修改就变成了子树内部的修改*/
12 #define R register int
13 #define AC 1001000
14 #define D printf("line in %d
",__LINE__);
15 #define LL long long
16 int n,root;
17 int date[AC],Next[AC],Head[AC],value[AC],tot;
18 LL ans,have;
19 LL f[AC];//f[i]代表节点i的子树内的时态已经被统一为了f[i]
20 bool z[AC],vis[AC];
21 inline int read()
22 {
23     int x=0;char c=getchar();
24     while(c > '9' || c < '0') c=getchar();
25     while(c >= '0' && c <= '9') x=x*10+c-'0',c=getchar();
26     return x;
27 }
28 
29 inline void add(int f,int w,int S)
30 {
31     date[++tot]=w,Next[tot]=Head[f],value[tot]=S,Head[f]=tot;
32     date[++tot]=f,Next[tot]=Head[w],value[tot]=S,Head[w]=tot;
33 }
34 
35 inline void pre()
36 {
37     R a,b,c;
38     n=read(),root=read();
39     for(R i=1;i<n;i++)
40     {
41         a=read(),b=read(),c=read();
42         add(a,b,c);
43     }
44 }
45 
46 void DFS(int x)//先统计一下
47 {
48     vis[x]=true;
49     R now;
50     bool done=false;
51     for(R i=Head[x]; i ;i=Next[i])
52     {
53         now=date[i];
54         if(vis[now]) continue;
55         if(!done) done=true;
56         have+=value[i];
57         DFS(now);
58         have-=value[i];
59     }
60     if(!done) f[x]=have;
61 }
62 
63 void DP(int x)
64 {
65     z[x]=true;
66     R now,cnt=0;
67     for(R i=Head[x]; i ;i=Next[i])
68     {
69         now=date[i];
70         if(z[now]) continue;
71         DP(now);
72         if(!f[x]) f[x]=f[now];
73         else if(f[now] != f[x])
74         {
75             if(f[now] < f[x]) ans+=f[x] - f[now];
76             else ans+=(f[now] - f[x]) * cnt,f[x]=f[now];
77         }//error!!!因为f[now]只代表新遍历到的子树，而f[x]则可能代表很多个子树
78         ++cnt;
79     }//error!!!于是如果统计让很多个子树暴力修改上来的代价，因为要修改很多边，因此要*cnt(f[x]中的子树个数)        
80 }
81 
82 int main()
83 {
84     freopen("in.in","r",stdin);
85     pre();
86     DFS(root);
87     DP(root);
88     printf("%lld
",ans);
89     fclose(stdin);
90     return 0;
91 }

[ZJOJ2007]时态同步 贪心

[ZJOJ2007]时态同步贪心