题解：CF813C The Tag Game

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！
代码很简单，缺省源写的比较长：

CPP

#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;
}

题解：CF813C The Tag Game

文章操作

相关推荐

评论

题解：CF813C The Tag Game