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

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

题目描述

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

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

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

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

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

定义两个点集 AABB 的字典序比较关系:设 AA 中的点按编号从小到大排序后是 a1,a2,...,aAa_1,a_2,...,a_{|A|}BB 中的点按编号从小到大排序后是 b1,b2,...,bBb_1,b_2,...,b_{|B|},那么定义 AABB 的字典序比较结果等于 {ai}\{a_i\}{bi}\{b_i\} 的字典序比较结果。

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

输入格式

第一行一个整数 nn

第二行一个整数 kk

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

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

第五行一个整数 I|I|

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

输出格式

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

样例

样例输入

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 # 分值 nn kk 特殊限制
1 66 20\le 20 1018\le 10^{18} 无特殊限制
2 1717 2000\le 2000 10000\le 10000 无特殊限制
3 2121 2000\le 2000 1018\le 10^{18} 无特殊限制
4 2727 106\le 10^6 1018\le 10^{18} 树是一条链
5 2929 106\le 10^6 1018\le 10^{18} 无特殊限制