树形DP
这题在考场上直接写的TreeDP……当时也没想出一个像样的暴力来对拍……好像只能这么直接做了……？
都说是博弈树了，转移关系都给的这么直接了……也没啥难度了吧= =（怪不得大家都不愿意写题解）
我的思路是这样的：
如果黑方想赢，那么：
1.在一个决策方为黑方的节点，对于它来说，最小黑方胜集合就是所有儿子中最小的那个 最小黑方胜集合
2.在一个决策方为白方的节点，它的最小黑方胜集合是所有儿子的最小黑方胜集合的并
那么现在我们就可以通过子节点的最小黑方胜集合，推出在某个节点状态下的最小黑方胜集合的大小，然而我们容易发现：哪些元素可能是最小黑方胜集合中的元素，也是满足这个转移的：
1.对每个节点维护一个mn[x]表示这个最小xx集合的大小，如果mn[son[i]]==mn[fa]，就把son的节点集合并入fa的，如果mn[son[i]]<mn[fa]，就把fa的节点集合改为son的。
第二种情况下的话直接并吧……$mn[fa]=\sum mn[son[i]]$
同理我们也能找出所有可能在最小白方胜集合中的叶节点……
求个并，随便搞搞出解即可
P.S.这题其实求树上某个节点的“最小黑方胜”集合内可能的节点时，求集合的并其实最简单的，拿链表搞搞就可以……但是蒟蒻不会写QAQ（没写过），加上昨天刚好考了一道可并堆的题目，就拿可并堆写了，权当复习……
/**************************************************************
Problem: 3164
User: Tunix
Language: C++
Result: Accepted
Time:648 ms
Memory:30304 kb
****************************************************************/ //Huce #6 B
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std; int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}
return v*sign;
}
typedef long long LL;
const int N=,INF=~0u>>;
/*******************tamplate********************/
int hd[N],to[N],ne[N],cnt;
void add(int x,int y){
to[++cnt]=y; ne[cnt]=hd[x]; hd[x]=cnt;
}
struct node{int v,l,r,dis;}t[N];
#define L t[x].l
#define R t[x].r
int n,m,black[N],white[N],rt[N],mn[N],tot,fa[N]; int merge(int x,int y){
if (!x || !y) return x+y;
if (t[x].v>t[y].v) swap(x,y);
R=merge(R,y);
if (t[L].dis<t[R].dis) swap(L,R);
t[x].dis=t[R].dis+;
return x;
}
bool sign[N];
void dfs(int x,bool now){
if (!hd[x]){
mn[x]=;
rt[x]=++tot;
t[tot].v=x;
t[tot].l=t[tot].r=t[tot].dis=;
return;
}
if (sign[x]==now) mn[x]=INF; else mn[x]=;
for(int i=hd[x];i;i=ne[i]){
sign[to[i]]=sign[x]^;
dfs(to[i],now);
if (sign[x]==now){
if (mn[x]>mn[to[i]]){
mn[x]=mn[to[i]];
rt[x]=rt[to[i]];
}else if (mn[x]==mn[to[i]]){
rt[x]=merge(rt[x],rt[to[i]]);
}
}else{
mn[x]+=mn[to[i]];
rt[x]=merge(rt[x],rt[to[i]]);
}
}
}
int ans[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("B.in","r",stdin);
// freopen("output.txt","w",stdout);
#endif
n=getint();
F(i,,n){
fa[i]=getint(); add(fa[i],i);
}
tot=; sign[]=;
dfs(,);
int num1=;
while(rt[]){black[++num1]=t[rt[]].v; rt[]=merge(t[rt[]].l,t[rt[]].r);}
sort(black+,black+num1+);
tot=; memset(rt,,sizeof rt);
dfs(,);
int num2=;
while(rt[]){white[++num2]=t[rt[]].v; rt[]=merge(t[rt[]].l,t[rt[]].r);}
sort(white+,white+num2+);
int num=;
for(int i=,j=;i<=num1 && j<=num2;i++){
while(black[i]>white[j] && j<=num2) j++;
if (black[i]==white[j]) ans[++num]=black[i];
}
int sum=;
F(i,,num) sum^=ans[i];
printf("%d %d %d\n",ans[],num,sum);
return ;
}
3164: [Heoi2013]Eden的博弈问题
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 110 Solved: 84
[Submit][Status][Discuss]
Description
对于有两个玩家的，状态透明且状态转移确定的博弈游戏，博弈树是常用的分析工具。博弈树是一棵有根树，其中的节点为游戏的状态。若节点B的父亲是A，则说
明状态A能通过一次决策转移到状态B。每个状态都有一个唯一的决策方，即这个状态下应该由哪一方做出决策。我们规定双方在任何时候都是轮流做出决策的，即
树上相邻节点的决策方总是不相同的。在这个问题中，我们只关心两个玩家的胜负情况，且规定游戏不会出现平局。
我们称两个玩家分别为黑方和白方，其中根节点的决策方为黑方。显然每个节点 只有两个状态：黑方胜和白方胜。若某内节点（即存在后继节点的节点）的决策
方为黑方，则该节点为黑方胜的充要条件为它的儿子中存在黑方胜的节点，反之亦然。求解博弈树即为判明博弈树根节点的状态。如果我们得知了所有叶节点（即无
后继节点的节点）的状态，那么博弈树就
很容易求解了。但是现在的情况是所有叶节点的状态均为未知的，需要进一步的计算。对于一个由叶节点构成的集合S，如果S中的节点均被判明为黑方胜，就可以
断言根节点为黑方胜的话，则称 S为一个黑方胜集合。对于黑方胜集合 S，
如果对于任意的黑方胜集合 S’均满足|S| ≤ |S’ |（|S|表示集合S中的元素数目），
则称S为一个最小黑方胜集合。同样地，也可以定义白方胜集合和最小白方胜集合。
Eden最近在研究博弈树问题。他发现，如果一个叶节点既属于某一个最小黑方胜集合，又属于一个最小白方胜集合，那么求解这个节点的状态显然最有益
于求解根节点的状态。像这样的叶节点就称之为关键叶节点。对于一棵给定的博弈树，Eden想要知道哪些叶节点是关键叶节点。
Input
每个测试点包含一组测试数据。
测试数据的第一行包含一个正整数n，表示博弈树的节点数目。节点从1到n 编号，且 1 号节点为根节点。
之后n–1 行，每行包含一个正整数。第i行的正整数表示节点i的父节点的编号。
Output
在一行内输出三个空格分隔的正整数，分别是编号最小的关键叶节点的编号，
关键叶节点的数目和所有关键叶节点的编号的异或和。
Sample Input
1
1
2
2
3
3
Sample Output
HINT
对于100% 的数据，1 ≤ n ≤ 200,000 ，且对于节点 i（i ≠ 1 ），其父节点的编号小于i。