题目传送门: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;
}