← 返回题目列表

Codeforces · 2143/C

C. 最大树

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 个顶点组成的树,编号从 $$$1$$$ 到 $$$n$$$。每条 $$$n - 1$$$ 边都与两个非负整数 $$$x$$$ 和 $$$y$$$ 相关联。

考虑整数$$$1$$$到$$$n$$$的排列$$$^{\text{*}}$$$ $$$p$$$,其中$$$p_i$$$表示分配给顶点$$$i$$$的值。

对于边 $$$(u, v)$$$,使得 $$$u \lt v$$$ 具有关联值 $$$x$$$ 和 $$$y$$$,其 贡献 定义如下: $$\begin{cases} x & \text{if } p_u \gt p_v, \\ y & \text{otherwise.} \end{cases}$$ 排列的

的 值 路径的 是所有边的贡献之和。

你的任务是找到满足以下条件的任意排列 $$$p$$$ 最大化 这个总值。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。

接下来的 $$$n - 1$$$ 行包含四个整数 $$$u$$$、$$$v$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \le u \lt v \le n$$$, $$$1 \le x, y \le 10^9$$$) — 描述顶点之间的边$$$u$$$ 和 $$$v$$$ 以及关联值 $$$x$$$ 和 $$$y$$$。保证给定的边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,您必须输出整数 $$$1$$$ 到 $$$n$$$ 的排列 $$$p$$$,以使问题中定义的总值最大化。如果有多个答案,您可以打印其中任何一个。

示例

输入
复制

3
3
1 2 2 1
2 3 3 2
5
1 2 1 3
1 5 2 1
2 4 5 7
2 3 1 100
5
2 5 5 2
3 5 4 6
4 5 1 5
1 5 3 5

输出
复制

3 2 1
2 3 5 4 1
1 5 2 3 4

注意

在第一个测试用例中:

考虑排列 $$$p = [3, 2, 1]$$$。它的价值是 $$$5 = 2 + 3$$$。原因如下:

  • 由于 $$$p_1 \gt p_2$$$,第一条边贡献 $$$+2$$$。
  • 由于 $$$p_2 \gt p_3$$$,第二条边贡献 $$$+3$$$。

其他一些排列的值如下:

  • $$$p = [1, 2, 3]$$$ 的值为 $$$1 + 2 = 3$$$。
  • $$$p = [1, 3, 2]$$$ 的值为 $$$1 + 3 = 4$$$。
  • $$$p = [3, 1, 2]$$$ 的值为 $$$2 + 2 = 4$$$。

在第二个测试用例中:

$$$p = [2, 3, 5, 4, 1]$$$ 的值为 $$$3 + 2 + 7 + 100 = 112$$$。另一个可能的正确答案是 $$$p = [2, 3, 4, 5, 1]$$$。