3964: 「LibreOJ NOI Round #1」验题
内存限制：1024 MB
时间限制：10.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
可爱的 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提示
数据范围：由于众所周知的原因，本题采用子任务制。每个子任务的情况如下表： | Subtask # | 分值 | $n$ | $k$ | 特殊限制 | | :----: | :----: | :----------: | :-------------: | :--------: | | 1 | $6$ | $\le 20$ | $\le 10^{18}$ | 无特殊限制 | | 2 | $17$ | $\le 2000$ | $\le 10000$ | 无特殊限制 | | 3 | $21$ | $\le 2000$ | $\le 10^{18}$ | 无特殊限制 | | 4 | $27$ | $\le 10^6$ | $\le 10^{18}$ | 树是一条链 | | 5 | $29$ | $\le 10^6$ | $\le 10^{18}$ | 无特殊限制 |