【每日一题】黑白树 题解

Description

一棵个点的有根树，号点为根，相邻的两个节点之间的距离为。树上每个节点i对应一个值。每个点都有一个颜色，初始的时候所有点都是白色的。
你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点，必须是白色的，然后到根的链上（包括节点与根）所有与节点距离小于的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。

Solution

很显然叶子节点是一定要选择的，但是被这些叶子节点能覆盖的点有时也是需要选择的，比如下面的这种情况。

虽然每次选择的节点一定要是白色节点，如果先选择了叶子节点就不能选择被这个节点覆盖的节点。但是可以先选择深度小的节点，这样再被覆盖也没问题，所以实际上这个点的选择是没有顺序的，而且也可以随意选择。

这样就是一个比较简单的dfs了，遍历到一个节点时，知道覆盖所有子节点的子树所需要的答案、子树中覆盖最大是多少、当前还能往父节点覆盖多少个节点，这样就可以知道遍历下去了。

要记往父节点转移的时候要减去边的长度即。

在dfs我选择返回一个tuple这样理论上能省一点内存。（实际好像没什么用，理解起来还复杂了）

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> edg[N]; // 邻接表存边
int k[N];
// tuple<答案, 若花费1可得最大覆盖, 此时最大覆盖>
tuple<int, int, int> dfs(int u) {
  int tot = 0, mx = k[u], far = 0;
  for(int i = 0; i < int(edg[u].size()); i++) {
    int a, b, c; tie(a, b, c) = dfs(edg[u][i]);
    // 把答案相加，覆盖值均取最大值
    tot += a, mx = max(mx, b - 1), far = max(far, c - 1);
  }
  // 若该节点不能被覆盖则需要花费1获得当前最大覆盖
  if(far == 0) tot++, far = mx;
  return make_tuple(tot, mx, far);
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n; cin >> n;
  for(int i = 2; i <= n; i++) {
    int fa; cin >> fa;
    edg[fa].push_back(i);
  }
  for(int i = 1; i <= n; i++) cin >> k[i];
  int res; tie(res, ignore, ignore) = dfs(1);
  cout << res << '\n';
}