CF1153D Serval and Rooted Tree（树形DP）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目链接：

https://www.luogu.org/problemnew/show/CF1153D

（cf崩了，贴了个落谷的）

题目大意：给你n个点，然后n-1条边，构成一棵树，每个点是子节点的最大值或最小值，将叶子节点填上整数（1~k，k为叶子节点的个数），使这棵树的根最大。

具体思路：对于每一个非叶子节点，假设他的值是x，如果这个点是取max，那么就要求这个节点的子节点中至少有一个是等于x的，其他都是小于x的。如果这个点是取min，那么就要求这个节点的子节点的值都是大于等于x的。然后再继续分析，我们把当前的节点赋值为他的子树中叶子节点的个数，那么当这个节点为取max的时候，我们就相当于他的所有子节点中取一个最大的就可以了。也就是相当于从子树中取一个最小消耗量。当为min的时候，当前节点的消耗量为他的所有子节点的消耗量之和。然后根节点的最大数就变成了k-num[1]+1.num[1]为根节点的消耗量。

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 # define inf 0x3f3f3f3f

 # define ll long long

 const int maxn = 3e5+;

 int col[maxn];

 vector<int>Edge[maxn];

 int tot=;

 int num[maxn];

 void  dfs(int u)

 {

     if(Edge[u].size()==)

     {

         tot++;

         num[u]=;

         return ;

     }

     if(col[u])

         num[u]=inf;

     else

         num[u]=;

     for(int i=; i<Edge[u].size(); i++)

     {

         int to=Edge[u][i];

         dfs(to);

         if(col[u])

             num[u]=min(num[to],num[u]);

         else

             num[u]+=num[to];

     }

     return ;

 }

 int main()

 {

     int n;

     scanf("%d",&n);

     for(int i=; i<=n; i++)

         scanf("%d",&col[i]);

     int tmp;

     for(int i=; i<=n; i++)

     {

         scanf("%d",&tmp);

         Edge[tmp].push_back(i);

     }

     dfs();

     printf("%d\n",tot-num[]+);

     return ;

 }