#P18806. [2027年国家集训队互测]枕清川

[2027年国家集训队互测]枕清川

枕清川

清川多雨,庭院的树枝上还系着昔日往来的短笺。临行前,你想把它们重新排好。

题目描述

给定一棵含 nn 个结点的有根树,编号为 1,2,…,n1,2,\ldots,n,根为 11。每个非根结点 ii 的父亲为 fai\mathrm{fa}_i。

把整数 11 至 nn 一一填入结点,要求每个父亲上的数严格小于任一儿子上的数。树上有 mm 个关键点。填完数后,将关键点上的数任意排列为长度 mm 的序列。求在所有合法填法及排列方式中,字典序最小的序列。

输入格式

第一行两个整数 n,mn,m。第二行是 fa2,…,fan\mathrm{fa}_2,\ldots,\mathrm{fa}_n,n=1n=1 时该行为空。第三行是 nn 个整数 aia_i;ai=1a_i=1 表示结点 ii 是关键点,ai=0a_i=0 表示不是。

输出格式

输出一行 mm 个正整数,以空格分隔,表示字典序最小的序列。

样例 1

7 3
1 1 2 2 3 6
0 0 0 1 1 0 1
3 4 7

例如,在结点 11 到 77 依次填入 (1,2,5,3,4,6,7)(1,2,5,3,4,6,7)。关键点 4,5,74,5,7 上的编号为 (3,4,7)(3,4,7),可以证明不存在更小的序列。

样例 2 至 8

样例 2 至 8 见样例附件中的 sample1.in/out 至 sample7.in/out,分别满足下表数据分组 1 至 7 的限制。

数据范围

1≤m≤n≤2⋅1051\le m\le n\le 2\cdot10^5,1≤fai<i1\le \mathrm{fa}_i<i,ai∈{0,1}a_i\in\{0,1\},∑iai=m\sum_i a_i=m。

以下分组用于说明数据性质;本题评测采用50个测试点,每点2分。

分组 参考分值 nn 上限 附加限制
1 5 2⋅1052\cdot10^5 m≤10m\le 10
2 15 性质 A
3 5 5000 性质 B
4 15 2⋅1052\cdot10^5
5 20 5000 无
6 15 5⋅1045\cdot10^4
7 25 2⋅1052\cdot10^5

性质 A:n−m≤20n-m\le 20。性质 B:除根外每个结点至多有一个儿子。