2143C.md (2734B)
1 Source: https://codeforces.com/problemset/problem/2143/C 2 3 C. Max Tree 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a tree consisting of $n$ vertices, numbered from $1$ to $n$. Each of the $n - 1$ edges is associated with two non-negative integers $x$ and $y$. 22 23 Consider a permutation$^{\text{∗}}$ $p$ of the integers $1$ through $n$, where $p_i$ represents the value assigned to vertex $i$. 24 25 For an edge $(u, v)$, such that $u \lt v$ with associated values $x$ and $y$, its contribution is defined as follows: $$ \begin{cases} x & \text{if } p_u \gt p_v, \\ y & \text{otherwise.} \end{cases} $$ 26 27 The value of the permutation is the sum of the contributions from all edges. 28 29 Your task is to find any permutation $p$ that maximizes this total value. 30 31 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 32 33 Input 34 35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 36 37 The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree. 38 39 Each of the next $n - 1$ lines contains four integers $u$, $v$, $x$, and $y$ ($1 \le u \lt v \le n$, $1 \le x, y \le 10^9$) — describing an edge between vertices $u$ and $v$ with associated values $x$ and $y$. It is guarranteed that the given edges form a tree. 40 41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 42 43 Output 44 45 For each test case, you must output a permutation $p$ of the integers $1$ through $n$ that maximizes the total value as defined in the problem. If there are multiple answers, you can print any of them. 46 47 Example 48 49 Input 50 51 ``` 52 3 53 54 3 55 56 1 2 2 1 57 58 2 3 3 2 59 60 5 61 62 1 2 1 3 63 64 1 5 2 1 65 66 2 4 5 7 67 68 2 3 1 100 69 70 5 71 72 2 5 5 2 73 74 3 5 4 6 75 76 4 5 1 5 77 78 1 5 3 5 79 ``` 80 81 Output 82 83 ``` 84 3 2 1 85 86 2 3 5 4 1 87 88 1 5 2 3 4 89 ``` 90 91 Note 92 93 In the first test case: 94 95 Consider the permutation $p = [3, 2, 1]$. Its value is $5 = 2 + 3$. Here's why: 96 97 * Since $p_1 \gt p_2$, the first edge contributes $+2$. 98 * Since $p_2 \gt p_3$, the second edge contributes $+3$. 99 100 The values of some other permutations are as follows: 101 102 * $p = [1, 2, 3]$ has value $1 + 2 = 3$. 103 * $p = [1, 3, 2]$ has value $1 + 3 = 4$. 104 * $p = [3, 1, 2]$ has value $2 + 2 = 4$. 105 106 In the second test case: 107 108 The value of $p = [2, 3, 5, 4, 1]$ is $3 + 2 + 7 + 100 = 112$. Another possible correct answer is $p = [2, 3, 4, 5, 1]$.