思路
可以看出，每次对一个点 \(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");
}