20200408 黑白树

20200408 黑白树

题意转化

在 个点中选择若干个点，将这些点的 级父亲以内全部染成黑色，求要把所有点染成黑色至少选多少点。

题解

考虑下面的这样一种情况

傻子才会选红色的点——绿色的点可以完全替代掉红色的点。

这样一来，可以等价为红色点 。

由此可以得到，一个点的 可以更换为自己子树中点 。

同时维护 代表覆盖 子树后还可以向上覆盖的最大距离，当 时需要选择点 。

实际上，这是一个贪心的过程。

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

template < typename Tp >
void read(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= fh;
}

const int maxn = 100007;
const int maxm = 200007;

int n;
int Head[maxn], to[maxm], Next[maxm], tot;
int k[maxn];

void addedge(int x, int y) {
    to[++tot] = y, Next[tot] = Head[x], Head[x] = tot;
}
void add(int x, int y) {
    addedge(x, y);
    addedge(y, x);
}

void Init(void) {
    read(n);
    for(int i = 2, x; i <= n; i++) {
        read(x);
        add(i, x);
    }
    for(int i = 1; i <= n; i++) read(k[i]);
}

int dp[maxn], ans;

void dfs(int x, int f) {
    for(int i = Head[x]; i; i = Next[i]) {
        int y = to[i];
        if(y == f) continue;
        dfs(y, x);
        k[x] = max(k[x], k[y] - 1);
        dp[x] = max(dp[x], dp[y] - 1);
    }
    if(dp[x] == 0) ++ans, dp[x] = k[x];
}

void Work(void) {
    dfs(1, 0);
    printf("%d\n", ans);
}

int main(void) {
    Init();
    Work();
    return 0;
}