自动搬运

查看原文

来自洛谷，原作者为

	Sliarae Re:start

搬运于2025-08-24 23:15:38，当前版本为作者最后更新于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$ 次，则答案为：

$$4(n - 1) - 2\sum\limits_{i = 2}^{n} [\text{high}_i < r] - \text{high}_1 $$

这个容易前缀和维护，单次询问 $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; 
}