#P17803. [Ontak2024]ROZ
[Ontak2024]ROZ
题目描述
给定一个连通无向简单图,顶点编号 到 ,边按输入顺序编号 到 。另外指定其中 条边,保证它们构成一棵生成树 。
为所有边赋权,使权值序列
恰为 的一个排列,并使指定的 成为图的最小生成树。
在所有满足条件的赋权中,求权值序列字典序最小的一个。比较的是按原边编号排列的权值。
输入格式
第一行两个整数 。
接下来 行,第 行两个整数 ,描述第 条边。
最后一行包含 个整数 ,为指定生成树的边编号。
输出格式
输出一行 个整数 。
数据范围
- 。
- ,。
- 无重边,原图连通。
- ,所列边组成连通的生成树。
样例 1
输入:
4 5
3 4
1 2
2 3
1 3
1 4
2 4 5
输出:
3 4 5 1 2
样例 2
输入:
4 4
1 2
1 4
2 3
3 4
1 3 4
输出:
1 4 2 3
子任务
| 编号 | 附加限制 | 分值 |
|---|---|---|
| 1 | 8 | |
| 2 | 18 | |
| 3 | 指定树是以顶点 为中心的星形树 | 9 |
| 4 | 指定树的边恰连接编号相邻的顶点,构成 | 12 |
| 5 | 17 | |
| 6 | 无附加限制 | 36 |