题解：P12449 [COTS 2025] 吸尘 / Usisavač

Sliarae · 2025-05-08 20:37:22 · 题解

设结点 i 的高度为 \text{high}_i，具体而言就是 i 到子树内叶子距离的最大值，i 的深度为 \text{dep}_i。

首先，假设我们最终停留在 e 点。我们强制它走回 1 点，构成一条回路，再将答案减去 \text{high}_1，也就是树高，因为最优策略是停留在深度最大的点。

假设某次询问给出一个 r，表示吸尘器的电缆长度为 r。

我们猜测最优策略是，沿着树的形状 dfs，假设我们现在位于 u，要走到 u 的一个儿子 v：

• 若 \text{high}_u \le r，就把吸尘器插在 u 的位置，将 u 子树内所有边都清理一遍，拔掉插座。

• 若 \text{high}_u > r，那么把吸尘器插在 u，将边 (u, v) 清理后回到 u，将插座拔掉后正常走到 v。

对于一条边 (v, fa_v)，易知若 \text{high}_v < r，则它会被经过 2 次，否则会被经过 4 次，则答案为：

这个容易前缀和维护，单次询问 O(1)。

现在我们通过说明，对于每条边 (v, fa_v)，若 \text{high}_v \ge r，则它至少被经过 4 次。

考虑它是如何被清理的，如果吸尘器在 v 子树外，那么清理时要经过边 (v, fa_v) 2 次，由 \text{high}_v \ge r，之后还要在 v 子树内插吸尘器，所以还要带吸尘器经过 2 次。

如果吸尘器在 v 子树内，可能会使得 v 向上 r 条边都少经过 2 次，但是最终停留的点的深度会减少 2r，所以还是不会变优。

#include <iostream>
#include <vector>

using namespace std;

const int kN = 3e5 + 5; 

int n, q;
vector<int> e[kN];
int dep[kN], high[kN], p[kN];

void Dfs (int u, int r) {
  for (auto v : e[u]) {
    if (v == r) continue;
    dep[v] = dep[u] + 1;
    Dfs(v, u);
    high[u] = max(high[u], high[v] + 1);
  }
}

int main () {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q;
  for (int i = 1, u, v; i < n; ++i) {
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  Dfs(1, 0);
  int mxd = 0; 
  for (int i = 1; i <= n; ++i) mxd = max(mxd, dep[i]);
  for (int i = 2; i <= n; ++i) ++p[high[i]];
  for (int i = 1; i <= n; ++i) p[i] += p[i - 1];
  for (int i = 1, r; i <= q; ++i) {
    cin >> r;
    cout << 4 * (n - 1) - mxd - 2 * p[r - 1] << ' ';
  }
  cout << '\n';
  return 0; 
}