本文主要是介绍题解：CF1975D（Paint the Tree），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题解：CF1975D（Paint the Tree）
看到有两个点在移动，好烦人！
那就直接“改题”：有一个点在一棵树上移动，每次可以移动到相邻的一个点，问至少要移动多少次才能够遍历整棵树。
这个题是不是似曾相识？显然 n n n 个点中，有一个点作为起点，还有一个点最后遍历，只需去一次，剩下的 n − 2 n - 2 n−2 个点则是要一去一回。为了使此时最少，我们考虑让最后遍历的那个点为离起点最远的点，设他们的距离为 d d d，则最少移动次数为 2 ( n − 1 ) − d 2 (n - 1) - d 2(n−1)−d。
我们再把题改回来：有两个点 a a a 和 b b b 在一棵树上移动，每次可以移动到相邻的一个点，问至少要移动多少次才能使得对于每一个点，都先被点 a a a 到过一次，再被点 b b b 到过一次。
如果在某一时间，只要有一个点已经满足条件，那么剩下的问题实际上就是刚才已经解决的问题，因为点 a a a 只需要按照和 b b b 相同的路径赶在 b b b 之前到达 b b b 将要到达的点，显然 b b b 只需要自顾自地遍历完整个图就 OK 了。
考虑让哪个点成为第一个满足条件的点。如果是按照让 a a a 和 b b b 相遇的最短路径设计，设他们的距离为 x x x，那么实际上这个点就是 b b b 按照这条路径走 ⌈ x 2 ⌉ \lceil \dfrac{x}{2} \rceil ⌈2x⌉ 次。但是这个点有可能不是最优。考虑更换法验证，如果存在某一种做法使得后面 b b b 遍历全图所用的操作数减少 1 1 1，那么显然至少要改变路径上的一个点，那么前一部分的答案就至少增加 1 1 1，因此可以证明选取这个点一定是最优的。
时间复杂度： O ( ∑ n ) O(\sum n) O(∑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];
}
这篇关于题解：CF1975D（Paint the Tree）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
