正题
题目链接:https://www.luogu.com.cn/problem/P4096
题目大意
一个博弈树，黑方先手。定义一个最小的叶子节点集为黑胜状态为黑方胜利集合，白色亦然。求所有既属于黑方胜利集合有属于白方胜利集合的点。
解题思路
设
f
i
,
0
/
1
f_{i,0/1}
fi,0/1表示
i
i
i子树中的最小黑发/白方胜利集和，然后可以根据这个求出所有的胜利集合点。
时间复杂度
O
(
n
)
O(n)
O(n)
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std
;
const int N
=2e5+10;
struct node
{
int to
,next
;
}a
[N
];
int n
,tot
,ls
[N
],f
[N
][2];
bool con
[N
][2];
void addl(int x
,int y
){
a
[++tot
].to
=y
;
a
[tot
].next
=ls
[x
];
ls
[x
]=tot
;return;
}
void dfs(int x
,int j
,int k
){
if(!ls
[x
]){f
[x
][k
]=1;return;}
if(j
!=k
)f
[x
][k
]=2147483647;
for(int i
=ls
[x
];i
;i
=a
[i
].next
){
int y
=a
[i
].to
;
dfs(y
,j
^1,k
);
if(j
!=k
)f
[x
][k
]=min(f
[x
][k
],f
[y
][k
]);
else f
[x
][k
]+=f
[y
][k
];
}
return;
}
void solve(int x
,int j
,int k
){
if(!ls
[x
])con
[x
][k
]=1;
for(int i
=ls
[x
];i
;i
=a
[i
].next
){
int y
=a
[i
].to
;
if(j
!=k
&&f
[y
][k
]!=f
[x
][k
])continue;
solve(y
,j
^1,k
);
}
return;
}
int main()
{
scanf("%d",&n
);
for(int i
=2;i
<=n
;i
++){
int x
;scanf("%d",&x
);
addl(x
,i
);
}
dfs(1,0,0);dfs(1,0,1);
solve(1,0,0);solve(1,0,1);
int ans1
=2147483647,ans2
=0,ans3
=0;
for(int i
=1;i
<=n
;i
++)
if(con
[i
][1]&&con
[i
][0])
ans1
=(ans1
<2147483647)?ans1
:i
,ans2
++,ans3
^=i
;
printf("%d %d %d\n",ans1
,ans2
,ans3
);
}
