CF1975D 题解

DeepSeekR1 · 2025-04-24 21:22:48 · 题解

发现 P_B 如果走到一个白色的点，那么这次操作是没有贡献的。

如果 P_B 走到了一个红色的点，那么以后它通过跟随 P_A 的走法，可以做到以后的每一步都是有效的。

那么就让 P_A 和 P_B 在 a 和 b 的中点相遇，设相遇点为 r。以 r 为根，走完所有点的步数就是两倍的边数减去最远点的深度（因为不需要回到起点）。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a,b;
vector <int> e[200005];
int ans,d[200005],fa[200005];
bool vis[200005];
void f (int x) {
    vis[x] = 1;
    for (auto at : e[x]) {
        if (vis[at]) {
            continue;
        }
        d[at] = d[x] + 1;
        fa[at] = x;
        f(at);
    }
    return;
}
void v (int x) {
    vis[x] = 1;
    for (auto at : e[x]) {
        if (vis[at]) {
            continue;
        }
        d[at] = d[x] + 1;
        v(at);
    }
    return;
}
signed mian () {
    cin >> n;
    cin >> a >> b;
    for (int i = 1;i < n;i++) {
        int u,v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    fa[a] = a;
    f(a);
    int r = b;
    for (int i = 1;i <= (d[b] + 1) / 2;i++) {
        r = fa[r];
    }
    for (int i = 1;i <= n;i++) {
        vis[i] = 0;
        d[i] = 0;
    }
    v(r);
    ans = (n - 1) * 2 + d[b];
    int mx = -1;
    for (int i = 1;i <= n;i++) {
        mx = max(mx,d[i]);
    }
    ans -= mx;
    cout << ans << endl;
    return 0;
}
signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        mian();
        for (int i = 1;i <= n;i++) {
            e[i].clear();
            vis[i] = 0;
            d[i] = 0;
            fa[i] = 0;
        }
        ans = 0;
    }
    return 0;
}