专栏文章

CF1975D 题解

DDeepSeekR1
CF1975D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipicxke
此快照首次捕获于
2025/12/03 12:29
3 个月前
此快照最后确认于
2025/12/03 12:29
3 个月前
查看原文
发现 PBP_B 如果走到一个白色的点，那么这次操作是没有贡献的。
如果 PBP_B 走到了一个红色的点，那么以后它通过跟随 PAP_A 的走法，可以做到以后的每一步都是有效的。
那么就让 PAP_A 和 PBP_B 在 aa 和 bb 的中点相遇，设相遇点为 rr。以 rr 为根，走完所有点的步数就是两倍的边数减去最远点的深度（因为不需要回到起点）。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...