#511. 「LibreOJ NOI Round #1」验题

内存限制:1024 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: immortalCO

题目描述

可爱的 WrongAnswer 非常喜欢独立集问题。在 CTSC2017 的论文答辩中,他就准备了一篇关于独立集的论文。

一天,他打算用这篇论文来出题。于是他想出了这样一道题:

给出一棵 n 个点的树 T=(V,E) 和一个独立集 I ,求出字典序比 I 恰好大 k 的那个独立集。

请参加 NOI 的您帮他验题。以下是一些可能会用到的定义:

一个独立集 I 是点集 V 的一个子集,满足 I 中任意两个点在 T 中不相邻,即不存在 x,y\in I 使得 (x, y)\in E (y, x)\in E

定义两个点集 A B 的字典序比较关系:设 A 中的点按编号从小到大排序后是 a_1,a_2,...,a_{|A|} B 中的点按编号从小到大排序后是 b_1,b_2,...,b_{|B|} ,那么定义 A B 的字典序比较结果等于 \{a_i\} \{b_i\} 的字典序比较结果。

T 的所有独立集按上述定义的字典序排序,如果 I 是其中排名第 x 的独立集,那么你需要求出的是排名第 x+k 的独立集。如果不存在这个独立集,则输出空集。

输入格式

第一行一个整数 n

第二行一个整数 k

第三行 n-1 个整数 x_1,x_2,...,x_{n-1} ,表示树上每条边的第一个端点(从 0 开始编号,下同);

第四行 n-1 个整数 y_1,y_2,...,y_{n-1} ,表示树上每条边的第二个端点;

第五行一个整数 |I|

第六行 |I| 个整数 I_1,I_2,...,I_{|I|} ,表示 I 中的每一个节点,保证 I 是一个合法的独立集。

输出格式

设你求出的独立集为 S (如果不存在满足要求的集合 S ,则令 S=\varnothing ),则你需要输出一行 |S| 个数,按照从小到大的顺序输出 S 中的每一个节点(从 0 开始编号)。

样例

样例输入

10
4
0 1 1 1 1 4 0 7 0
1 2 3 4 5 6 7 8 9
3
5 8 9

样例输出

6 7 9

更多样例

见附加文件或备用网盘链接(提取码:q5bs

数据范围与提示

由于众所周知的原因,本题采用子任务制。每个子任务的情况如下表:

Subtask # 分值 n k 特殊限制
1 6 \le 20 \le 10^{18} 无特殊限制
2 17 \le 2000 \le 10000
3 21 \le 10^{18}
4 27 \le 10^6 树是一条链
5 29 无特殊限制