题目详情题解（0）讨论（0）提交记录（0）

CF2107D.Apple Tree Traversing

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一棵 nn 个点的苹果树，每个结点上有一棵苹果。你有一张白纸。

你将要在苹果树上穿梭，重复做以下事情直到苹果树上没有苹果：

  • 选择一条路径 (u,v)(u,v)，满足这条路径上所有点上都有苹果。
  • 拿走这条路径上的所有苹果，设你这次拿了 dd 个苹果，在你的纸上依次写下三个数字 dd，uu 和 vv。

称结束后你的纸上的数字构成的数列为 aa。输出可能的字典序最大的 aa。

输入格式

多组数据，第一行一个整数 t(1≤t≤104)t(1\le t\le 10^4) 表示数据组数。

对于每组数据，第一行一个整数 n(1≤n≤1.5×105)n(1\le n\le 1.5\times 10^5)。
接下来 n−1n-1 行，每行两个数字表示树上的一条边。

保证一个测试点中 ∑n≤1.5×105\sum n\le 1.5\times 10^5。

输出格式

每组数据输出一行，为可能的字典序最大的 aa。可以证明 aa 的长度 ≤3×n\le 3\times n。

输入输出样例

  • 输入#1

    6
4
1 2
1 3
1 4
4
2 1
2 4
2 3
5
1 2
2 3
3 4
4 5
1
8
6 3
3 5
5 4
4 2
5 1
1 8
3 7
6
3 2
2 6
2 5
5 4
4 1

    输出#1

    3 4 3 1 2 2 
3 4 3 1 1 1 
5 5 1 
1 1 1 
5 8 7 2 4 2 1 6 6 
5 6 1 1 3 3

说明/提示

在第一组数据中，我们进行以下操作：

  • 选择路径 (4,3)(4,3)，拿走结点 1,3,41,3,4 上面的苹果，在纸上写下 3,4,33,4,3。
  • 选择路径 (2,2)(2,2)，拿走结点 22 上面的苹果，在纸上写下 1,2,21,2,2。

最终形成了 a=(3,4,3,1,2,2)a=(3,4,3,1,2,2)，可以证明这是字典序最大的合法结果。

By chenxi2009

输入解题思路，AI测评打分。不知道怎么写?

首页