题目链接:传送门
一个很贪心的数位dp
显然从叶节点开始染色是优的
因为相比更靠上的节点来说会染到更多的节点
那就先去染叶节点,在他的父亲节点处判断是否被覆盖
如果父亲不能被覆盖那就ans++,否则更新父亲节点能覆盖到的最远点
#include <bits/stdc++.h>
#define
using namespace std;
typedef long long ll;
struct node {int next, to;}e[A];
int head[A], num;
void add(int fr, int to) {e[++num].next = head[fr]; e[num].to = to; head[fr] = num;}
int n, fa[A], k[A], ans;
int dfs(int fr) {
int maxx = 0;
for (int i = head[fr]; i; i = e[i].next) {
int ca = e[i].to;
if (ca == fa[fr]) continue;
maxx = max(maxx, dfs(ca));
}
if (maxx <= 1) {ans++; return k[fr];}
k[fa[fr]] = max(k[fa[fr]], k[fr] - 1);
return maxx - 1;
}
int main(int argc, char const *argv[]) {
cin >> n;
for (int i = 2; i <= n; i++) scanf("%d", &fa[i]), add(i, fa[i]), add(fa[i], i);
for (int i = 1; i <= n; i++) scanf("%d", &k[i]);
dfs(1); cout << ans << endl;
}