NC13249

题意

给你一棵树，每个节点 $i$i上有一个值 $k\left[i\right]$k[i]，一开始树上所有节点均为白色，要求你每次选择一个白色节点染色，从该节点往根的链上小于 $k\left[i\right]$k[i]的均被染色，求最小染色次数为多少？

思路

DFS 贪心
首先叶子结点是一定要染色的，我们考虑如何返回的时候构造最优方案，我们维护两个数组。
回溯路径所能染色到的最远距离 $k\left[x\right]=max\left(k\right[x],k[s]-1)$k[x]=max(k[x],k[s]−1)
无须染色所能染色到的最远距离 $d\left[x\right]=max\left(d\right[x],d[s]-1)$d[x]=max(d[x],d[s]−1)
当 $d\left[x\right]=0$d[x]=0的时候，意味着到该节点必须进行一次染色，此时不一定是选择该节点进行染色，可以选择回溯路径所能染色到的最远距离那个点进行染色。

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

int n,f[N],k[N],d[N],res;
vector<int>G[N];

void dfs(int x,int fa){
	for(int i=0;i<G[x].size();i++){
		int s=G[x][i];
		dfs(s,x);
		k[x]=max(k[x],k[s]-1);
		d[x]=max(d[x],d[s]-1);
	}
	if(!d[x]) ++res,d[x]=k[x];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=2;i<=n;i++){
		int x; cin>>x;
		G[x].push_back(i);
	}
	for(int i=1;i<=n;i++){
		cin>>k[i];
	}
	dfs(1,-1);
	cout<<res<<'\n';
	return 0;
}