CF2143C.Max Tree

给定一棵包含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。树的每一条边都关联着两个非负整数 $x$ 和 $y$。

考虑 $1$ 到 $n$ 的一个排列 $p$，其中 $p_i$ 表示分配给顶点 $i$ 的值。

对于一条边 $(u, v)$，满足 $u < v$ 且关联的值为 $x$ 和 $y$，其贡献定义如下：

$$\begin{cases} x & \text{如果 } p_u > p_v, \\ y & \text{否则。} \end{cases}$$

该排列的值为所有边的贡献之和。

你的任务是找出任意一个使得总值最大的排列 $p$。

注：长度为 $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 < v \le n$，$1 \le x, y \le 10^9$），表示一条连接 $u$ 和 $v$ 的边，以及其关联的值 $x$ 和 $y$。保证这些边构成一棵树。

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

对于每个测试组，输出一个 $1$ 到 $n$ 的排列 $p$，最大化题目定义的总值。若有多解，输出任意一个均可。

样例解释：

第一组测试：

考虑排列 $p = [3, 2, 1]$，其值为 $5 = 2 + 3$，具体如下：

• 由于 $p_1 > p_2$，第一条边贡献 $+2$。
• 由于 $p_2 > 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]$。

由 ChatGPT 5 翻译