【Foreign】红与蓝 [暴力]

红与蓝

Time Limit: 10 Sec Memory Limit: 256 MB

Description

Input

Output

Sample Input

　　2
　　2
　　0 1
　　-1 -1
　　2
　　0 1
　　-1 1

Sample Output

　　1 2
　　-1

HINT

Main idea

　　每个节点有红色、蓝色或者无色，给定了若干叶子节点的颜色，非叶子节点的颜色定义为所有儿子中颜色出现次数最多的一个，若一样则无色。叶子节点无色则可以染色，红色先手，蓝色接着轮流染色，最后若根为红色则胜利否则失败。胜利的话还要求输出可行方案。

Source

　　我们可以先O(n)求出在不动叶子节点情况下每一个点的颜色，由于每个一个点只有奇数个儿子，且红色先手。那么这时候如果根节点为红色或者无色则必胜，蓝色则必败。

　　然后我们分情况讨论，蓝色就直接输出“-1”，结束即可。如果根是红色的话，显然染色对于答案是没有什么影响的，所以所有无色的叶子节点都可以是解。

　　现在我们来讨论根无色的情况：我们计算每一个点中儿子的蓝色个数和红色个数，如果一个点是 （蓝色，且蓝色个数=红色个数+1） 或者 （无色，蓝色个数=红色个数）则可以往下递归，找到叶子节点为无色则可以是解。我们来解释一下：

　　1. 蓝色，蓝色个数=红色个数+1：如果往下走有可染色的叶子节点，那么必然逼着蓝色接着染，否则蓝色就输了。这个点的颜色就会是：无、蓝、无……由于红色先手，所以最后这个点是可以变成无色的，因为递归做到这里，所以这个点的父亲节点是白色的，然后这个点变为了白色，它的父亲就少了一个蓝色儿子，就变成红色了。

　　2. 无色，蓝色个数=红色个数：如果往下走有可染色的叶子节点，那么这一条无色链上都会变成红色的，显然可行。

　　这样我们暴力递归往下讨论，就解决了这个问题。

Code

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 const int ONE = ;

 int T;

 int n,x,root;

 int Val[ONE];

 int next[ONE],first[ONE],go[ONE],tot;

 int ans_num,Ans[ONE];

 void Add(int u,int v)

 {

         next[++tot]=first[u];    first[u]=tot;    go[tot]=v;

 }

 int get()

 {

         int res,Q=;    char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 void Deal_first(int u)

 {

         for(int e=first[u];e;e=next[e])

         {

             int v=go[e];

             Deal_first(v);

             Val[u] += Val[v];

         }

         if(Val[u] < ) Val[u] = -;

         else if(Val[u] > ) Val[u] = ;

 }

 void Dfs(int u)

 {

         if(!Val[u] && !first[u])

         Ans[++ans_num] = u;

         for(int e=first[u];e;e=next[e])

         {

             int v=go[e];

             int tot=;

             for(int i=first[v];i;i=next[i])

                 tot+=Val[go[i]];

             if(tot== || tot==-) Dfs(v);

         }

 }

 void Solve()

 {

         n=get();

         tot=; memset(first,,sizeof(first));

         for(int i=;i<=n;i++)

         {

             x=get();

             if(!x) root=i;

             else Add(x,i);

         }

         for(int i=;i<=n;i++)

         {

             Val[i]=get();

             if(Val[i]==) Val[i]=;

             else if(Val[i]==) Val[i]=-;

             else Val[i]=;

         }

         Deal_first(root);

         if(Val[root] < )

         {

             printf("-1");

             return;

         }

         else

         {

             ans_num=;

             if(Val[root]==) Dfs(root),sort(Ans+,Ans+ans_num+);

             if(Val[root]==) for(int i=;i<=n;i++) if(!Val[i] && !first[i]) Ans[++ans_num]=i;

             printf("%d ",ans_num);

             for(int i=;i<=ans_num;i++)

                 printf("%d ",Ans[i]);

         }

 }

 int main()

 {

         T=get();

         while(T--)

             Solve(),printf("\n");

 }

巴特西