题解
对于硬币数变为零的点,由于既不能穿越,也不能选取,所以等于删掉了
所以操作就变成了,选取一个点,删除以其为根的树的所有叶子节点
先将树退化成链,考虑链上操作的情况,如果选取链上端点,总节点数只减一,否则减二
因此对于树上任意一条链,每次选取会导致要么减一要么减二,因此只考虑最长链的长度
当链的长度剩2的时候,只能减一,所以先手输,其他情况先手赢
code
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;
vector<ll> G[200005];
ll depth[200005]={0};
ll root,maxs=0;
void dfs(ll now,ll fa)
{
depth[now]=depth[fa]+1;
if(depth[now]>maxs)
{
maxs=depth[now];
root=now;
}
for(auto next:G[now])
{
if(next==fa) continue;
dfs(next,now);
}
}
void solve()
{
ll n;
cin>>n;
for(ll i=1;i<n;i++)
{
ll x,y;
cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1,1);
maxs=0;
depth[root]=0;
dfs(root,root);
if(depth[root]%3==2) cout<<"Second\n";
else cout<<"First\n";
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int TT=1;
//cin>>TT;
while(TT--) solve();
return 0;
}
标签:Removing,ll,Coins,dfs,depth,maxs,now,root
From: https://www.cnblogs.com/pure4knowledge/p/18334814