#P5265. 啊

啊

题目描述

有一棵以 11 为根的树。每个叶节点最初处于 无名、有名、未标记三种状态之一。所有非叶节点最初都未标记。

无名 和 有名 轮流选择一个未标记的叶节点,并将其标记为自己。无名 先手。所有叶节点都已标记后,从叶子向根确定非叶节点的标记:该节点取所有直接子节点中出现次数较多的标记。每个非叶节点都有奇数个子节点,所以不会平局。根的标记决定获胜者。

在双方都采取最优策略时,判断 无名 能否获胜。若能获胜,求她第一步可以选择的所有必胜叶节点。

输入格式

第一行一个整数 TT,表示数据组数。每组数据三行。

  1. 一个整数 nn,表示节点数,节点编号为 1,…,n1,\ldots,n。
  2. nn 个整数 f1,…,fnf_1,\ldots,f_n,其中 fif_i 是节点 ii 的父节点,f1=0f_1=0。父节点编号可以大于子节点编号。
  3. nn 个整数 g1,…,gng_1,\ldots,g_n。gi=0g_i=0 表示 无名,gi=1g_i=1 表示 有名,gi=−1g_i=-1 表示未标记。非叶节点的初始标记均为 −1-1。

输出格式

每组数据输出一行。若 无名 无法获胜,输出 -1。否则输出必胜首步的数目 mm,再按节点编号严格升序输出这 mm 个叶节点。只判断胜负时,可在获胜的数据组输出 0,也可按升序输出已找到的必胜首步子集。所有数据组胜负判断均正确时,即使必胜首步不全,也能获得该测试点的一半分数。

样例

2
2
0 1
-1 -1
2
0 1
-1 1
1 2
-1

原题另在选手目录提供样例 2。

数据范围

  • 20%20\% 的数据满足 1≤n≤201\le n\le20,T=1T=1。
  • 60%60\% 的数据满足 1≤n≤20001\le n\le2000。
  • 所有数据满足 1≤n≤1051\le n\le10^5,1≤T≤101\le T\le10。

原 PDF 题面