#P10300. [2023年重庆八中NOI模拟]简单题

    ID: 9418 传统题 2500ms 888MiB 尝试: 9 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-贡献法奇偶性分析二分查找堆贪心链表排列构造

[2023年重庆八中NOI模拟]简单题

简单题(perm)

题目描述

zzh 有一棵 nn 个点的树,在这棵树上有一个棋子,这个棋子初始在点 11 。棋子只能沿着树边移动。

cjz 有一个 n−1n-1 阶排列 pp 。某一天夜晚,cjz 来到了 zzh 的树前。他依次执行了 nn 步操作:

在前 n−1n-1 步操作中,第 ii 步他将棋子从当前位置沿着最短路径移动到了点 pi+1p_i+1。

在最后一步操作中,他将棋子从当前位置沿着最短路径移动到了点 11。

第二天早上,zzh 发现了 cjz 的操作。她得出了这个棋子在 cjz 操作的过程中经过的边的条数 kk ,但她不知道 cjz 的排列。zzh 把这个问题交给了你。因此你需要求出任意一个满足按照这个排列操作,操作的过程中经过的边的条数为 kk 的排列。如果不存在这样的排列,你需要告诉 zzh 她求出了错误的 k。

然而,cjz 连续 TT 天在夜晚进行了这样的操作。因此你需要在每一天早上回答 zzh 的问题。同时,神仙的树每天都会发生变化,因此每天的树都会改变,但每天 cjz 操作前棋子都在位置 11。

即在 TT 天中的每一天,给出 nn,一棵 nn 个点的树以及 kk ,你需要求出任意一个 n−1n-1 阶排列 pp 满足如下条件或报告无解:

∑i=0n−1dis(pi+1,pi+1+1)=k\sum_{i=0}^{n-1}dis(p_{i}+1,p_{i+1}+1)=k

这里 dis(i,j)dis(i,j) 为两点在树上的最短路径经过的边数, 认为 p0=pn=0p_0=p_n=0。

输入格式

从文件 perm.in 读入。

输入第一行包含一个整数 TT ,表示询问的天数。接下来若干行依次表示每一天的情况:

对于每一天:

首先一行包含两个正整数 n,kn,k ,含义见题面。

然后 n−1n-1 行,每行两个正整数 ai,bia_i,b_i ,表示这棵树的所有边。

输出格式

输出到文件 perm.out。

输出 TT 行,每一天输出一行,按照输入的顺序输出每一天:

如果这一天的询问不存在合法的排列,则这一行输出一个数 −1-1。

否则这一行输出 n−1n-1 个以单个空格分隔的正整数 p1,...,n−1p_{1,...,n-1} ,表示你求出的排列。

本题使用SPJ,但你可以输出额外的行末空格和文末回车。

样例
样例输入1
2
5 10
1 2
2 3
3 4
3 5
5 12
1 2
2 3
3 4
3 5
样例输出1
4 2 1 3
-1
样例解释1

对于第一组数据:

$dis(1,5)=3,dis(5,3)=1,dis(3,2)=1,dis(2,4)=2,dis(4,1)=3$

因此它们的和为 1010,满足条件。

对于第二组数据,经过验证不存在满足条件的排列。

样例输入/输出 2~5

见下发文件

样例 1∼51\sim 5 依次满足测试点 2,4,6,8,102,4,6,8,10 的限制。

需要注意的是,下发文件中的 .ans 文件中的输出只代表所有解中的一组解。但你可以输出任意一组满足要求的解。

数据范围与限制

对于所有数据,保证 $3\leq n\leq 10^6,\sum n\leq 2\times 10^6,k\leq 10^{12}$,输入的边构成一棵树。

测试点编号 特殊限制
11 T=0T=0
2,32,3 n≤9,T≤5n\leq 9,T\leq 5
4,54,5 n≤13,T≤5n\leq 13,T\leq 5
6,76,7 ∑n≤2000\sum n\leq 2000,第 ii 条树边连接 (i,i+1)(i,i+1)
8,98,9 ∑n≤2000\sum n\leq 2000,任意两点间路径经过的边数不超过 33
10,1110,11 ∑n≤2000\sum n\leq 2000
12,1312,13 ∑n≤2×105\sum n\leq 2\times 10^5,第 ii 条树边连接 (i,i+1)(i,i+1)
14,1514,15 ∑n≤2×105\sum n\leq 2\times 10^5,任意两点间路径经过的边数不超过 33
16,17,1816,17,18 ∑n≤2×105\sum n\leq 2\times 10^5
19,2019,20 无特殊限制

友情提示:读入不规范,爆零两行泪。

本题需要输入/输出优化