【每日一题】树形dp专题 Minimax Tree 题解

Description

给出一棵树，除了叶子节点外要给其他节点打上 k 个 min 和 n - l - k 个 max 的 tag ，要求根节点的 max状态下最大可能值, min状态下最小可能值。

Solution

在所有节点必须放满的情况下，要么是叶子，要么是max/min
在贪心的条件下，如果只考虑要求最大值
最优的策略是把 max 放在深度较低的地方，即先取 min 再取 max 结果更优
于是考虑dfs，如果当前深度小于 n - l - k，就放 max， 否则放 min
最小值也可以相应处理。
注意观察样例，如果某一个节点只有一个儿子，则我们直接传到儿子，不需要考虑深度增加的问题，具体看一下代码。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
typedef long long ll;
int a[N], son[N], l, n, k;
vector<int> G[N];
ll dfs(int u, int par, int dep, bool solve_type) {
  //cout << "path:" << u << ' ' << par << endl;
  if(a[u]) {
    return a[u];
  } else if(son[u] == 1) {
    for(auto &v : G[u]) {
      if(v == par) continue;
      return dfs(v, u, dep, solve_type);
    }
  } else if(solve_type) { // 求最大值
    if(dep >= n - l - k) {
      ll ans = 1e18;
      for(auto &v : G[u]) {
        if(v == par) continue;
        ans = min(ans, dfs(v, u, dep + 1, solve_type));
      }
      return ans;
    } else {
      ll ans = 0;
      for(auto &v : G[u]) {
        if(v == par) continue;
        ans = max(ans, dfs(v, u, dep + 1, solve_type));
      }
      return ans;
    }
  } else { // 求最小值
    if(dep >= k) {
      ll ans = 0;
      for(auto &v : G[u]) {
        if(v == par) continue;
        ans = max(ans, dfs(v, u, dep + 1, solve_type));
      }
      return ans;
    } else {
      ll ans = 1e18;
      for(auto &v : G[u]) {
        if(v == par) continue;
        ans = min(ans, dfs(v, u, dep + 1, solve_type));
      }
      return ans;
    }
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> k;
  for(int i = 2; i <= n; i++) {
    int u; cin >> u;
    G[i].push_back(u); 
    G[u].push_back(i);
    son[u]++;
  }
  for(int i = 1; i <= n; i++) cin >> a[i], l += (a[i] > 0);
  cout << dfs(1, 0, 0, false) << ' ' << dfs(1, 0, 0, true) << "\n";
  return 0;
}