题解：CF1975D（Paint the Tree）

题解：CF1975D（Paint the Tree）

看到有两个点在移动，好烦人！

那就直接“改题”：有一个点在一棵树上移动，每次可以移动到相邻的一个点，问至少要移动多少次才能够遍历整棵树。

这个题是不是似曾相识？显然 $n$ 个点中，有一个点作为起点，还有一个点最后遍历，只需去一次，剩下的 $n-2$ 个点则是要一去一回。为了使此时最少，我们考虑让最后遍历的那个点为离起点最远的点，设他们的距离为 $d$，则最少移动次数为 $2(n-1)-d$。

我们再把题改回来：有两个点 $a$ 和 $b$ 在一棵树上移动，每次可以移动到相邻的一个点，问至少要移动多少次才能使得对于每一个点，都先被点 $a$ 到过一次，再被点 $b$ 到过一次。

如果在某一时间，只要有一个点已经满足条件，那么剩下的问题实际上就是刚才已经解决的问题，因为点 $a$ 只需要按照和 $b$ 相同的路径赶在 $b$ 之前到达 $b$ 将要到达的点，显然 $b$ 只需要自顾自地遍历完整个图就 OK 了。

考虑让哪个点成为第一个满足条件的点。如果是按照让 $a$ 和 $b$ 相遇的最短路径设计，设他们的距离为 $x$，那么实际上这个点就是 $b$ 按照这条路径走 $\lceil \frac{x}{2}\rceil$ 次。但是这个点有可能不是最优。考虑更换法验证，如果存在某一种做法使得后面 $b$ 遍历全图所用的操作数减少 $1$，那么显然至少要改变路径上的一个点，那么前一部分的答案就至少增加 $1$，因此可以证明选取这个点一定是最优的。

时间复杂度：$O(\sum n)$，可以通过此题。

代码：

#include <bits/stdc++.h>
#define N 220000
using namespace std;
int t, n, a, b, x, y;
vector<int> edge[N];
int d[N], f[N], q[N];
int bfs(int from, int to);
int main() {scanf("%d", &t);while (t--) {scanf("%d%d%d", &n, &a, &b);for (int i = 1; i <= n; i++) {edge[i].clear();}for (int i = 1; i < n; i++) {scanf("%d%d", &x, &y);edge[x].push_back(y);edge[y].push_back(x);}int ans = bfs(a, b), id = b;for (int i = 1; i <= ans; i++) {id = f[id];}ans += 2 * (n - 1) - bfs(id, -1);printf("%d\n", ans);}return 0;
}
int bfs(int from, int to) {for (int i = 1; i <= n; i++) {d[i] = -1;f[i] = -1;}int front = 1, rear = 0;rear++;q[rear] = from;d[from] = 0;f[from] = 0;while (front <= rear) {int now = q[front];front++;for (int i : edge[now]) {if (d[i] == -1) {d[i] = d[now] + 1;f[i] = now;rear++;q[rear] = i;}}}if (to != -1) {return (d[to] + 1) / 2;}int ret = 1;for (int i = 2; i <= n; i++) {if (d[i] > d[ret]) {ret = i;}}return d[ret];
}