[atcoder2376] black and white tree (game)

The question

A and B Dye the nodes on the tree in turn ,A Every time you choose the untainted spots, dye them white ,B Every time you choose to dye the untainted dots into black , Finally, if all white is adjacent to black , be B - , otherwise A - . Both sides adopt the optimal strategy , seek A Win or lose B - .

Answer key

A First, select the parent of the leaf node u, be B Only leaf nodes can be selected （ Otherwise, after the leaf nodes are dyed white , Can never be next to black ）, therefore , If there is u There are more than two leaf nodes , be A - ;
And then delete u, be u Father v, If v No child nodes ,v It becomes a new leaf node ,A You can continue with the previous operation ,B Always be passive .
When there are two situations ,A A winning

• The current node u Contains two or more leaf nodes
• if u Root , And u All child nodes of are dyed white （ Then you can dye yourself white ）

dfs Just deal with one side .

Code

#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;// Marked as leaf node  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;// Leaf node is greater than or equal to 2 if(f==0&&(int)adj[u].size()==cnt[1]) return true;// At present u Root ,u All child nodes of are white  if(cnt[0]) col[u]=1;// If there are leaf nodes , This one is dyed white  else col[u]=0;// All the child nodes of this point are dyed white （ Deleted ）, At present u Become a leaf node  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; }