暑假集训Day10 C (树形DP)

题目链接在这里:Problem - C - Codeforces

树形DP很重要的一点就是要倒着做,就是自底向上。当时正着做想了半天没想出来硬是没想着能倒着搞……  树形DP因为要考虑完孩子节点再考虑当前节点,所以要先遍历再操作。

对于每一个点都有两个限制条件,一个是到当前点能抓到的人数一定>=孩子节点能抓到的人数。另一个是当前子树人数之和平均分到每一个叶子结点上取整(这个不一定能做到,但是如果做不到,那出来的答案一定比上一个限制条件小)

自顶向下讨论是从繁到简的讨论,非常的阴间,我们的讨论应该是从简至繁,从最简单的情况一步步推到最复杂的情况,所以应该从后向前讨论。

下次如果卡住了从前向后讨论的时候可以想着从后向前讨论。

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=2e5+5;
 4 typedef long long LL;
 5 LL n;
 6 LL tot,head[MAX],adj[MAX<<1],nxt[MAX<<1];
 7 LL ans[MAX],val[MAX],son[MAX],in[MAX];
 8 void addedge(int u,int v){
 9     tot++;
10     adj[tot]=v;
11     nxt[tot]=head[u];
12     head[u]=tot;
13 }
14 void dfs1(LL x,LL fa){
15     //if (in[x]==0) son[x]=1;
16     LL i,j;bool flag=true;
17     for (i=head[x];i;i=nxt[i]){
18         if (adj[i]==fa) continue;
19         dfs1(adj[i],x);
20         flag=false;
21         son[x]+=son[adj[i]];
22         val[x]+=val[adj[i]];
23         ans[x]=max(ans[x],ans[adj[i]]);
24     }
25     if (flag) son[x]=1;
26     ans[x]=max(ans[x],(val[x]-1)/son[x]+1);
27 }
28 
29 int main(){
30     freopen ("c.in","r",stdin);
31     freopen ("c.out","w",stdout);
32     LL i,j,x;
33     scanf("%lld",&n);
34     memset(head,0,sizeof(head));
35     memset(in,0,sizeof(in));
36     memset(ans,0,sizeof(ans));
37     for (i=2;i<=n;i++){
38         scanf("%lld",&x);
39         addedge(i,x);
40         addedge(x,i);
41         in[x]++;
42     }
43     for (i=1;i<=n;i++) scanf("%lld",val+i);
44     bool flag=true;
45     for (i=1;i<=n;i++) if (val[i]!=0) {flag=false;break;}
46     if (flag) {printf("0");return 0;}
47     dfs1(1,0);
48     printf("%lld",ans[1]);
49     return 0;
50 }

 

上一篇:day10


下一篇:day10-Git