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

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

题目描述

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

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

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

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

一个独立集 III 是点集 VVV 的一个子集,满足 III 中任意两个点在 TTT 中不相邻,即不存在 x,y∈Ix,y\in Ix,yI 使得 (x,y)∈E(x, y)\in E(x,y)E(y,x)∈E(y, x)\in E(y,x)E

定义两个点集 AAABBB 的字典序比较关系:设 AAA 中的点按编号从小到大排序后是 a1,a2,...,a∣A∣a_1,a_2,...,a_{|A|}a1,a2,...,aABBB 中的点按编号从小到大排序后是 b1,b2,...,b∣B∣b_1,b_2,...,b_{|B|}b1,b2,...,bB,那么定义 AAABBB 的字典序比较结果等于 {ai}\{a_i\}{ai}{bi}\{b_i\}{bi} 的字典序比较结果。

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

输入格式

第一行一个整数 nnn

第二行一个整数 kkk

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

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

第五行一个整数 ∣I∣|I|I

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

输出格式

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

样例

样例输入

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 # 分值 nnn kkk 特殊限制
1 666 ≤20\le 2020 ≤1018\le 10^{18}1018 无特殊限制
2 171717 ≤2000\le 20002000 ≤10000\le 1000010000 无特殊限制
3 212121 ≤2000\le 20002000 ≤1018\le 10^{18}1018 无特殊限制
4 272727 ≤106\le 10^6106 ≤1018\le 10^{18}1018 树是一条链
5 292929 ≤106\le 10^6106 ≤1018\le 10^{18}1018 无特殊限制