【NOI五连测】[D2T1] 啊

题目传送门:http://pan.baidu.com/s/1hsLh92W
OJ传送门:http://oi.cdshishi.net:8080/Problem/1712

这一道题,我一眼看到的时候,也是“啊”的。博弈论?不会啊QAQ
最后只能打了暴力,结果还打错了QAQ

来说一说正解。
我们定义三种节点:
1.无名必胜
2.有名必胜
3.先手必胜

再来讨论一下这三种节点间的关系:
假如一个节点的儿子中,1、2两种类型的节点一样多,则为类型3
否则,1、2哪种多,该节点就是那种节点

于是搞一个树形DP,就可以搞出根节点的类型
显然,如果是类型3,则无解
如果是类型2,则只有部分节点可选
如果是类型1,则全部的叶子结点都可选

另外,本题还要注意,因为非叶子结点的颜色,最终会取决于它儿子节点的颜色
所以,第一步走的节点,一定是叶子结点,否则,并没有什么卵用QAQ

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN = 100000+9;

int n,vout,que[MAXN],type[MAXN],num[MAXN][3];
vector<int> G[MAXN];

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

inline void init(){
	n = read();
	for (int i=1;i<=n;i++) G[i].clear(), num[i][0] = num[i][1] = num[i][2] = 0;
	for (int i=1;i<=n;i++) G[read()].push_back(i);
	for (int i=1;i<=n;i++) type[i] = read() + 1;
	
	int fro,bak; que[fro=bak=1] = 1;
	while (fro < n) {
		int w = que[bak++];
		for (int i=0;i<(int)G[w].size();i++)
			que[++fro] = G[w][i];
	} 
}

void GetAns(int w){
	if ((int)G[w].size() == 0) {
		if (type[w] == 0) que[++vout] = w;
	} else {
		int t = num[w][2] - num[w][1];
		if (t <= 1 && t >= 0) for (int i=0;i<(int)G[w].size();i++)
			GetAns(G[w][i]);
	}
}

int main(){
	freopen("ah.in","r",stdin);
	freopen("ah.out","w",stdout);
	int T; cin>>T;
	while (T--) {
		init();
		for (int k=n,i=que[k];k;i=que[--k]){
			if ((int)G[i].size() == 0) continue;
			else { 
				for (int j=0;j<(int)G[i].size();j++) num[i][type[G[i][j]]]++;
				if (num[i][2] == num[i][1]) type[i] = 0;
				else if (num[i][1] > num[i][2]) type[i] = 1;
				else type[i] = 2;
			}
		} if (type[1] == 1) {
			int tot = 0; for (int i=1;i<=n;i++) if ((int)G[i].size() == 0 && type[i] == 0) que[++tot] = i;
			printf("%d ",tot); for (int i=1;i<=tot;i++) printf("%d ",que[i]); cout<<endl;
		} else if (type[1] == 0) {vout = 0, GetAns(1); sort(que+1,que+1+vout); cout<<vout<<' '; for (int i=1;i<=vout;i++) cout<<que[i]<<' '; cout<<endl;}  
		else printf("-1\n"); 
	}
	return 0;
}