【CodeM初赛B轮】A 贪心

【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 <cstdio>

#include <cstring>

#include <iostream>

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;

}