【CodeM初赛B轮】A

题目大意：给你一棵树，起初所有点都是白色的，你每次都能选择一个白点i，将这个点i到根路径上的所有到i的距离<k[i]的点都染成黑色（根和i也算，已经被染成黑色的点还是黑色）。问最少需要染多少次才能将所有点都变黑。

n<=100000

题解：显然贪心啊，但是我一开始居然写了树剖。。。

因为叶子节点是一定要染的，所以我们可以将所有点按DFS序排序，从后往前染。记录vis[i]，表示之前已经将所有到i的距离<=vis[i]的点染成了黑色；再维护mx[i]，表示之前染过的点最多能将到i的距离<=mx[i]的点染成黑色。然后用当前的vis和mx去更新fa就行了。

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=100010;int n,cnt,ans;int fa[maxn],tag[maxn],k[maxn],p[maxn],head[maxn],nxt[maxn],to[maxn],ml[maxn];void add(int a,int b){	to[cnt]=b,nxt[cnt]=head[a],head[a]=cnt++;}void dfs(int x){	p[++p[0]]=x;	for(int i=head[x];i!=-1;i=nxt[i])	dfs(to[i]);}int main(){	scanf("%d",&n);	int i,a;	memset(head,-1,sizeof(head));	for(i=2;i<=n;i++)	scanf("%d",&fa[i]),add(fa[i],i);	for(i=1;i<=n;i++)	scanf("%d",&k[i]);	dfs(1);	for(i=n;i>=1;i--)	{		a=p[i];		ml[a]=max(ml[a],k[a]);		if(!tag[a])	tag[a]=ml[a],ans++;		ml[fa[a]]=max(ml[fa[a]],ml[a]-1),tag[fa[a]]=max(tag[fa[a]],tag[a]-1);	}	printf("%d",ans);	return 0;}