【每日一题】4月8日 黑白树

基本思路

• 由于每个点只能往上更新，所以dfs一遍从叶子结点开始往根结点做选择。
• 但需要注意如下图所示的情况：当我们dfs回溯到红色的结点时，发现已经选过的结点都无法更新到该结点，那么是直接选择该结点继续往上更新吗？
• 答案是否定的，因为很明显我们选择权值为10的结点更优，也就是说当某个结点无法被已选择的结点更新时，可能在其子树中存在更优解。
• 若，则结点比结点更优，其中表示结点的权值，表示到的路径长度，是的孩子。
• 可以先dfs一遍获得每个结点的最优解，再dfs一遍求需要操作的最小次数，但显然两次dfs可以合并成一次。
  

代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;

int n, x;
int k[MAXN];
int dp[MAXN], ans;
struct Edge {
    int v, ne;
} edge[MAXN];
int head[MAXN], tot;
void init() {
    ans = tot = 0;
    memset(dp, 0, sizeof(dp));
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v) {
    edge[tot].v = v;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
void dfs(int id) {
    for(int i = head[id]; i != -1; i = edge[i].ne) {
        dfs(edge[i].v);
        dp[id] = max(dp[id], dp[edge[i].v] - 1);
        k[id] = max(k[id], k[edge[i].v] - 1);
    }
    if(dp[id] == 0) {
        ans++;
        dp[id] = k[id];
    }
}
int main() {
    init();
    scanf("%d", &n);
    for(int i = 2; i <= n; i++) {
        scanf("%d", &x);
        addedge(x, i);
    }
    for(int i = 1; i <= n; i++) scanf("%d", &k[i]);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}