题解归档 - cf813C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf813C
• 本地来源：problems/cf813C/idea.md
• 题目链接：https://codeforces.com/contest/813/problem/C
• 原始标题：CF813C — The Tag Game

思路

CF813C — The Tag Game

题意

根为 1 的树，Alice 在 1，Bob 在 x。Bob 先手，轮流移动（可停留）。Alice 到达 Bob 所在点游戏结束；Alice 最小化总步数，Bob 最大化。

做法

两次 BFS：p[v] 为 1 到 v 距离，s[v] 为 x 到 v 距离。

Bob 与 Alice 各走 k 步后，Bob 能到 v 当且仅当 s[v] <= k；Alice 能到 v 当且仅当 p[v] <= k。Bob 希望最大化 k。

Alice 会先沿 1→x 逼近；Bob 相对 x 只有 p[v]-p[x] 的领先去躲进侧枝。可达条件：s[v] <= p[v] - p[x]（不是 s[v] <= p[v]）。

答案：2 * max{ p[v] | s[v] <= p[v] - p[x] }。

验证

样例 1/2 + stress.py -n 200（brute 为带深度限制的 minimax）。

代码

来源：problems/cf813C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:48:33
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
vector<ll>ss[maxn];
ll p[maxn],s[maxn],vis[maxn];
ll n,x,i,j,k,ans,cur,pd;
int main(){
    cin>>n>>x;
    for(i=1;i<n;i++){
        cin>>j>>k;
        ss[j].push_back(k);
        ss[k].push_back(j);
    }
    queue<ll>q;
    q.push(1);
    vis[1]=1;
    p[1]=0;
    while(!q.empty()){
        cur=q.front();
        q.pop();
        for(j=0;j<(ll)ss[cur].size();j++){
            pd=ss[cur][j];
            if(!vis[pd]){
                vis[pd]=1;
                p[pd]=p[cur]+1;
                q.push(pd);
            }
        }
    }
    for(i=1;i<=n;i++) vis[i]=0;
    q.push(x);
    vis[x]=1;
    s[x]=0;
    while(!q.empty()){
        cur=q.front();
        q.pop();
        for(j=0;j<(ll)ss[cur].size();j++){
            pd=ss[cur][j];
            if(!vis[pd]){
                vis[pd]=1;
                s[pd]=s[cur]+1;
                q.push(pd);
            }
        }
    }
    ans=0;
    for(i=1;i<=n;i++){
        if(s[i]<=p[i]-p[x]) ans=max(ans,p[i]);
    }
    cout<<2*ans<<"\n";
    return 0;
}