Max Tree

The whole trick is to stop thinking about the permutation values as exact numbers.

For an edge $(u,v)$ with $u < v$:

• if $p_u > p_v$, we get $x$;
• otherwise, since values are distinct, $p_u < p_v$, and we get $y$.

So every edge only cares about the relative order of its two endpoints.

Best choice per edge

For each edge, we obviously want the bigger of $x$ and $y$.

If $x > y$, then this edge wants:

$p_u > p_v$

So vertex $u$ should appear earlier if we sort vertices from largest value to smallest value.

If $y > x$, then this edge wants:

$p_v > p_u$

So vertex $v$ should appear earlier.

If $x = y$, the edge does not care. Pick either direction; it changes nothing.

This gives us one ordering constraint per edge. For example, if an edge wants $p_a > p_b$, draw a directed edge:

$a \to b$

meaning: $a$ must receive a larger value than $b$.

Why can we satisfy every edge?

Usually, constraints like this can conflict. For example, if we had:

$1 \to 2,\quad 2 \to 3,\quad 3 \to 1$

then we would be cooked, because that asks for:

$p_1 > p_2 > p_3 > p_1$

which is impossible.

But here the original graph is a tree.

A tree has no undirected cycles. A directed cycle would also require an undirected cycle underneath it. Since there is no undirected cycle, there cannot be a directed cycle either.

So after orienting every tree edge however we want, the result is always a DAG.

That means a topological ordering always exists.

Building the permutation

After directing edges, run a topological sort.

Suppose the topological order is:

$ord_1, ord_2, \dots, ord_n$

For every directed edge $a \to b$, $a$ appears before $b$ in this order.

Now assign values like this:

$p_{ord_i} = n - i + 1$

So earlier vertices get larger values.

Then for every directed edge $a \to b$:

$p_a > p_b$

which is exactly what that edge wanted.

Therefore every edge contributes:

$\max(x,y)$

The total value becomes:

$\sum_{edges} \max(x,y)$

No permutation can do better than that, because each edge individually contributes at most $\max(x,y)$. Since we reach that upper bound for every edge, the permutation is optimal. Boom. The tree did all the heavy lifting.

Algorithm

For each test case:

1. Read the tree.
2. For each edge $(u,v,x,y)$ with $u < v$:
   • if $x \ge y$, add directed edge $u \to v$;
   • otherwise, add directed edge $v \to u$.
3. Topologically sort this directed graph.
4. Assign values from $n$ down to $1$ along the topological order.
5. Print the resulting permutation.

Complexity

Each edge is processed once, and topological sorting is linear.

Time complexity:

$O(n)$

per test case.

Memory complexity:

$O(n)$