Serval and Rooted Tree

题目链接

题目大意

给一棵有根树，设有k个叶子节点，给所有的叶子节点标号1~k；然后每个非叶子节点都有一个得到当前节点标号的方法，就是取他的所有子节点的最大值或最小值（取决于输入）；问根节点能得到的最大的标号是啥。

刚开始不会做，想着贪心可不可以做，于是想了半天，啥求都不会

于是瞅了一眼题解，dp做，向来不怎么dp的我很是懵逼，还是不知道怎么dp，于是又看了看，如下：
dp[i] 表示第i个节点的标号是他所有子节点标号中的第几大，也就是1~k中比它大的数至少有dp[i] - 1个
于是
叶子结点的dp值就是1。
如果操作是得到子节点的最大值，那么当前的dp值就等于子节点的dp值之和。
如果操作是得到子节点的最大值，那么当前的dp值就等于子节点的dp值的最小值，为什么是最小值？因为要是当前节点的值最大，比当前节点大的数越少越好，所以是最小值。
害~ 把maxn看错还re了一发。
代码:
这个代码其实dfs里不用fa标记的，因为题目给出树的时候直接给的是它的父亲节点是谁，并且是个有根树，所以就建单向边就好，并没有当前节点到父节点的边。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 3e5+5;
vector<int> vv[maxn];
int dp[maxn];
int a[maxn];
int s =0 ;
void dfs(int x,int fa)
{
   
	int sum = 0;
	int f = 0;
	int maxx = maxn;
	for(int i = 0; i < vv[x].size(); i ++ )
	{
   
		int v = vv[x][i];
		if(v == fa)
			continue;
		f = 1;
		dfs(v,x);
		sum += dp[v];
		maxx = min(maxx, dp[v]);
	}
	if(f == 0)
	{
   
		s ++ ;
		dp[x] = 1;
	}
	else if(a[x] == 1)
	{
   
		dp[x] = maxx;
	}
	else
		dp[x] = sum;
// printf("%d %d\n",x,dp[x]);
}


int main()
{
   
	int n;
	scanf("%d",&n);
	for (int i = 1; i <= n; i ++ )
	{
   
		scanf("%d",&a[i]);
	}
	for (int i = 2; i <= n; i ++ )
	{
   
		int x;
		scanf("%d",&x);
		vv[x].push_back(i);
	}
	dfs(1,0);
// printf("%d\n",s);
	printf("%d\n",s - dp[1] + 1);
}