题意:
一棵根节点为1的树,告诉初始每个结点的颜色(黑或白),两个人轮流操作,规则是,选择一个黑色节点变为白色,在选择当前点到根节点路径上的任意个点(可以为没有),将其颜色翻转,最后不能操作的人输。
题解:
将每次操作这样理解,将一个黑点变白,然后将操作的点(不包含)到根节点路径上的点变成任意的状态。
结论是如果树的所有层的黑点的个数是偶数,则先手必败。
为什么?
因为全是偶数,先手造作第k层的点后,那么k层的点就变为奇数了(留给后手一个必胜的状态),这时后手也操作k层的一个点,然后复制先手的操作,一定可以留给先手一个全是偶数的状态。
这样,一定是后手走完最后一步,先手必败。
代码:
#include<bits/stdc++.h>
#define N 1010
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi acos(-1.0)
#define mod 998244353
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
int w[N],t[N],dep[N];
vector<int>a[N];
void dfs(int x,int fa,int d)
{
dep[x]=d;
if(w[x]) t[d]++;
for (auto i:a[x]) if (i!=fa) dfs(i,x,d+1);
}
int main()
{
int n;sc(n);
for (int i=1;i<=n;i++) sc(w[i]);
for (int i=1;i<n;i++)
{
int j,k;
scc(j,k);
a[j].pb(k);a[k].pb(j);
}
dfs(1,-1,1);
int ans=0;
for (int i=1;i<=n;i++)
if (w[i])
{
if (t[dep[i]]&1) {ans=1;break;}
}
if (ans) cout<<"First";else cout<<"Second";
}