#P18806. [2027年国家集训队互测]枕清川
[2027年国家集训队互测]枕清川
枕清川
清川多雨,庭院的树枝上还系着昔日往来的短笺。临行前,你想把它们重新排好。
题目描述
给定一棵含 个结点的有根树,编号为 ,根为 。每个非根结点 的父亲为 。
把整数 至 一一填入结点,要求每个父亲上的数严格小于任一儿子上的数。树上有 个关键点。填完数后,将关键点上的数任意排列为长度 的序列。求在所有合法填法及排列方式中,字典序最小的序列。
输入格式
第一行两个整数 。第二行是 , 时该行为空。第三行是 个整数 ; 表示结点 是关键点, 表示不是。
输出格式
输出一行 个正整数,以空格分隔,表示字典序最小的序列。
样例 1
7 3
1 1 2 2 3 6
0 0 0 1 1 0 1
3 4 7
例如,在结点 到 依次填入 。关键点 上的编号为 ,可以证明不存在更小的序列。
样例 2 至 8
样例 2 至 8 见样例附件中的 sample1.in/out 至 sample7.in/out,分别满足下表数据分组 1 至 7 的限制。
数据范围
,,,。
以下分组用于说明数据性质;本题评测采用50个测试点,每点2分。
| 分组 | 参考分值 | 上限 | 附加限制 |
|---|---|---|---|
| 1 | 5 | ||
| 2 | 15 | 性质 A | |
| 3 | 5 | 5000 | 性质 B |
| 4 | 15 | ||
| 5 | 20 | 5000 | 无 |
| 6 | 15 | ||
| 7 | 25 |
性质 A:。性质 B:除根外每个结点至多有一个儿子。