[LOJ6175] 「美团 CodeM 初赛 Round B」黑白树[树形DP]

每次从当前的叶子往上DP（每条链上没有染色的深度最大点视为叶子），先看子树里的点能不能染到这个点，染不到就++ans,把这个点的k传上去，能染到的话要chmax(k[fa[u]], k[u]-1)

vint G[MAXN];
int k[MAXN], fa[MAXN], ans;
inline int dfs(int u) {
  int cur = 0;
  for (int i = 0; i < G[u].size(); i++) 
    chmax(cur, dfs(G[u][i]));
  if (cur <= 1) return ++ans, k[u];
  chmax(k[fa[u]], k[u] - 1);
  return cur - 1;
}
int main() {
  int n; 
  scanf("%d", &n);
  lop(i, 2, n) scanf("%d", fa + i), G[fa[i]].pb(i);
  lop1(i, n) in, k[i];
  ans = 0;
  dfs(1);
  out, ans;
  return 0;
}

[LOJ6175] 「美团 CodeM 初赛 Round B」黑白树[树形DP]

原文：https://www.cnblogs.com/storz/p/10348324.html