思路
可以看出,每次对一个点 \(u\) 操作一次,就相当于删除以 \(u\) 为根的所有叶节点。
当然我们还是没有什么思路,我们可以想简单一点:在一条链上的情况。
-
如果 \(u\) 是链的端点:以 \(u\) 为根节点的叶节点只有一个,所以链的长度减一。
-
如果 \(u\) 不是链的端点:以 \(u\) 为根节点的叶节点有两个,所以链的长度减二。
而我们可以看出,在树上找到最长链,即树的直径。根据树的直径性质,如果我们操作直径上的点,旁边的分支也会被删完。
题目已被简化为,一个数 \(n\),每次减 \(1\) 或 \(2\),谁减到 \(0\),谁就赢了。(小学奥数题)
\(n \equiv 2 \ (mod \ 3)\) 的时候后手有必胜策略,其他时候先手有必胜策略。
特别的,我们树的直径求的是点不是边,所以注意要 \(+1\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,maxx,dis[N];
int head[N],to[N*2],nxt[N*2],idx;
void add(int x,int y){to[++idx]=y,nxt[idx]=head[x],head[x]=idx;}
void dfs(int x,int fa)
{
if(dis[x]>dis[maxx])maxx=x;
for(int i=head[x];i;i=nxt[i])
{
if(to[i]==fa)continue;
dis[to[i]]=dis[x]+1;
dfs(to[i],x);
}
}
int main()
{
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(1,0);
memset(dis,0,sizeof dis);
dfs(maxx,0);
if(dis[maxx]%3+1==2)printf("Second");
else printf("First");
}
标签:head,idx,int,题解,Coins,为根,AGC033C,节点,dis
From: https://www.cnblogs.com/gdfzlcx/p/17764315.html