建立平台网站需要花多少钱/方象科技服务案例

题意

A和B轮流给树上的结点染色，A每次选择没染过的点染成白色，B每次选择没染过的点染成黑色，最后若所有白色都与黑色相邻，则B胜，否则A胜。双方以最优策略，求A胜还是B胜。

题解

A首先选择叶子结点的父亲u，则B只能选择叶子结点（否则叶子节点染白后，永远不可能与黑色相邻），所以，如果存在u有两个以上叶子结点，则A胜；
然后删去u，则u的父亲v，如果v没有了子节点，v就成为新的叶子结点，A可继续先前的操作，B永远处于被动当中。
当遇到一下两种情况时，A必胜

• 当前结点u含有两个或以上叶子结点
• 若u为根，且u的所有子节点都被染为白色（这时把自己染为白色即可）

dfs处理一边即可。

代码

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=100005;int N;
vector<int> adj[MAXN];
int col[MAXN];bool dfs(int u,int f)
{if(adj[u].size()==1U){col[u]=0;//标记为叶子结点return false;}int cnt[2]={0};for(int i=0;i<(int)adj[u].size();i++){int v=adj[u][i];if(v==f)continue;if(dfs(v,u))return true;cnt[col[v]]++;}if(cnt[0]>=2)return true;//叶子结点大于等于2if(f==0&&(int)adj[u].size()==cnt[1])return true;//当前u为根，u的所有子节点均为白色if(cnt[0])col[u]=1;//如果有叶子结点，这个点染白elsecol[u]=0;//这个点的子节点全部被染白（被删去），当前u变为叶子结点return false;
}int main()
{scanf("%d",&N);for(int i=1;i<N;i++){int u,v;scanf("%d%d",&u,&v);adj[u].push_back(v);adj[v].push_back(u);}if(N==2)puts("Second");else{bool ans;for(int i=1;i<=N;i++)if(adj[i].size()>1U){ans=dfs(i,0);break;}puts(ans?"First":"Second");}return 0;
}