题解：P17056 [NWERC 2022] 高质量树 / High-quality Tree

· · 题解

我们需要找到最小的叶子移除数量，使得给定有根二叉树的所有子树都满足平衡条件。一个子树是平衡的，当且仅当其左右子树的深度差不超过 1。N 最大为 2\cdot 10^5 。问题的核心是：对于树中任意节点 u，我们必须决定保留 u 下方的结构，使其平衡，并记录所需的最小移除代价。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
using VI = vector<int>;
const int NN = 2e5 + 4;
int Sz[NN], F[NN];  // Sz[u]:子树u大小; F[u]:可构成的强平衡树的最大深度
VI G[NN];
int dfs(int u = 1, int fa = 0) {  // 计算Sz和F
  Sz[u] = F[u] = 1;               // 初始化：自己算一个节点，深度至少为1
  int f0 = 0, f1 = 0;             // 记录两个子节点的F值
  for (int v : G[u])
    if (v != fa)  // 递归处理子节点, 累加子树大小
      Sz[u] += dfs(v, u), (f0 ? f1 : f0) = F[v];  // 将子节点的F值存入f0和f1
  F[u] = min(f0, f1) + (f0 != f1) + 1;
  return Sz[u];  // 子树深度相同，新深度为f0+1, 否则为min(f0,f1)+2
}
// 计算最少移除节点数,d: 父节点给予的深度限制
int dfs1(int u, int fa, int d) {
  if (d == 0) return Sz[u];  // 如果深度限制为0，必须移除整个子树
  int r = 0;                 // 记录需要移除的节点数
  for (int v : G[u])         // 递归计算每个子树需要移除的节点数
    if (v != fa)             // v的深度限制是min(d-1, F[v])
      r += dfs1(v, u, min(d - 1, F[v]));
  return r;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n;
  cin >> n;
  for (int i = 1, u, v; i < n and cin >> u >> v; i++)
    G[u].push_back(v), G[v].push_back(u);
  dfs(), printf("%d\n", dfs1(1, 0, F[1]));
  return 0;
}