题解：CF813C The Tag Game

Take_A_Single_6 · 2024-11-20 16:00:25 · 题解

duel 秒掉的简单博弈题。
令 h_x 为节点 x 子树的最大深度，显然祖先 h_{fa}>h_{now}，所以我们考虑最多能跳到哪个祖先。
令 dep_x 为 x 的深度：

• 若 dep_x 为奇数，应该跳到 \frac{dep_x+1}{2}+1，因为再往上跳刚好会被下一步碰上。
• 若 dep_x 为偶数，应该跳到 \frac{dep_x}{2}+1，因为再往上就是 Alice 了。

往上跳的过程可以倍增实现，然后再往子树最深的节点跳就可以了。
注意：奇数还有两步，因为 Alice 要去碰到 Bob！
代码很简单，缺省源写的比较长：

#include<bits/stdc++.h>
#define int long long
#define db double
#define maxn 1000005
#define mod 998244353
#define fir first
#define sec second
#define pr pair<int,int>
#define mk make_pair
#define pb push_back
#define inf 10000000000000000
using namespace std;
inline int read()
{
    int SS=0,WW=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')WW=-1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        SS=(SS<<1)+(SS<<3)+(ch^48);
        ch=getchar();
    }
    return SS*WW;
}
inline void write(int XX)
{
    if(XX<0)putchar('-'),XX=-XX;
    if(XX>9)write(XX/10);
    putchar(XX%10+'0');
}
int n,m,ans,dep[maxn],h[maxn],f[maxn][21];
vector<int>e[maxn];
void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1,f[u][0]=fa;
    for(int i=1;i<=20;i++)f[u][i]=f[f[u][i-1]][i-1];//倍增
    for(int v:e[u])
    {
        if(v==fa)continue;
        dfs(v,u),h[u]=max(h[u],h[v]+1);
    }
    h[u]=max(h[u],1ll);//注意叶节点
}
signed main()
{
    int x,y,t,M;
    n=read(),M=m=read();
    for(int i=1;i<n;i++)x=read(),y=read(),e[x].pb(y),e[y].pb(x);
    dfs(1,0),t=(dep[m]+1)/2+1;//最多跳到的高度
    for(int i=20;i>=0;i--)
        if(dep[f[m][i]]>=t)m=f[m][i];
    write((dep[M]-dep[m]+h[m]+(dep[M]&1))*2);//注意奇数
    return 0;
}