#P5265. 啊
啊
题目描述
有一棵以 为根的树。每个叶节点最初处于 无名、有名、未标记三种状态之一。所有非叶节点最初都未标记。
无名 和 有名 轮流选择一个未标记的叶节点,并将其标记为自己。无名 先手。所有叶节点都已标记后,从叶子向根确定非叶节点的标记:该节点取所有直接子节点中出现次数较多的标记。每个非叶节点都有奇数个子节点,所以不会平局。根的标记决定获胜者。
在双方都采取最优策略时,判断 无名 能否获胜。若能获胜,求她第一步可以选择的所有必胜叶节点。
输入格式
第一行一个整数 ,表示数据组数。每组数据三行。
- 一个整数 ,表示节点数,节点编号为 。
- 个整数 ,其中 是节点 的父节点,。父节点编号可以大于子节点编号。
- 个整数 。 表示 无名, 表示 有名, 表示未标记。非叶节点的初始标记均为 。
输出格式
每组数据输出一行。若 无名 无法获胜,输出 -1。否则输出必胜首步的数目 ,再按节点编号严格升序输出这 个叶节点。只判断胜负时,可在获胜的数据组输出 0,也可按升序输出已找到的必胜首步子集。所有数据组胜负判断均正确时,即使必胜首步不全,也能获得该测试点的一半分数。
样例
2
2
0 1
-1 -1
2
0 1
-1 1
1 2
-1
原题另在选手目录提供样例 2。
数据范围
- 的数据满足 ,。
- 的数据满足 。
- 所有数据满足 ,。