#2191. travel
travel
travel
题目描述
标题: travel - Problem - QOJ.ac
The problem was used in the following contests:
本来这里应该有一份符合出题人 2022 年时写题面的风格(大概来说就是很长)的题目背景,但出题人某天晚上交作业的时候被酒店阴间的Wifi质量恶心到了,同时出题人的笔记本坏了,因此他并没能在ddl前写出这样的背景。
小 Z 有一棵 n 个节点的树,树的第 i 条边连接点 ui,vi。
小 Z 想要找到一个 排列 或者 环排列,使得从排列的第一个点出发按照排列的顺序访问所有点后,总共经过的边数正好是 k。
具体来说,给定 op∈{1,2},你需要找到一个 n 阶排列 p,满足如下条件:
- 如果 op=1,你需要满足 ∑i=1n−1dis(pi,pi+1)=k。
- 如果 op=2,你需要满足 ∑i=1ndis(pi,p(i mod n)+1)=k。
这里 dis(x,y) 为树上 x,y 节点间最短路径经过的边数。
小 Z 完全不会 OI,因此他希望你能找到一组解,或者告诉他不存在这样的解。如果有多个可能的解,你可以输出任意一个满足条件的解。
小 Z 有 T 个这样的问题,你需要回答小 Z 的每一个问题。
输入格式
输入文件第一行包含一个非负整数 T,表示数据组数,接下来依次给出每组数据。
对于一组数据,第一行包含三个正整数 n,k,op,表示树的点数以及小 A 要求的总路程,还有小 A 的询问类型。
接下来 n−1 行,每行包含两个正整数 ui,vi,依次表示树的每一条边。
输出格式
对于每组数据,输出一行:
如果这组数据中不存在满足要求的排列,则输出一个数 −1。
否则,在这一行中输出 n 个整数 p1,⋯,pn,表示你找到的排列。
样例
样例输入 #1
3
5 7 1
1 2
1 3
2 4
2 5
4 6 1
1 2
1 3
1 4
1 0 1
样例输出 #1
3 4 2 1 5
-1
1
对于第一组数据,可以发现 dis(3,4)=3,dis(4,2)=1,dis(2,1)=1,dis(1,5)=2,因此它满足小 Z 对于排列的要求。
对于第二组数据,可以证明不存在解。
对于第三组数据,显然唯一的一种方案满足条件。
样例输入 #2
3
5 10 2
1 2
1 3
2 4
2 5
4 6 2
1 2
1 3
1 4
1 0 2
样例输出 #2
3 4 2 1 5
1 2 3 4
1
这组样例的情况与上一组类似,唯一的区别在于 op=2,因此此时计算距离时需要额外计算 dis(p1,pn)。
数据范围与限制
对于所有数据,保证 T≤5×105,1≤n≤5×105,∑n≤5×105,0≤k≤n2,op∈{1,2},1≤ui,vi≤n,给出的边构成一棵合法的树。
在一个子任务中,如果你正确地回答了所有 op=1 的询问或者所有 op=2 的询问,但没有正确回答所有询问,则你可以获得 50% 的分数。
注意:如果你只想获得 op=1 或 op=2 部分的分数,你也需要在剩余数据上输出符合格式的内容。任意一组数据上输出格式错误将 可能导致整个子任务获得 0 分。
测试点编号 测试点分数 特殊限制 1 2 T=0 2 4 T≤5,n≤9 3 8 T≤5,n≤13 4 14 第 i 条边连接 (i,i+1),∑n≤2000 5 10 第 i 条边连接 (i,i+1) 6 12 T≤5,n≤30 7 18 ∑n≤2000 8 10 n≤4×104,∑n≤105 9 22 无特殊限制
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3
5 7 1
1 2
1 3
2 4
2 5
4 6 1
1 2
1 3
1 4
1 0 1
3 4 2 1 5
-1
1