P4787 [BalkanOI 2018] Minmaxtree

**Translated from [BalkanOI 2018](http://boi2018.ro) Day 1 T3 “[Minmaxtree](http://boi2018.ro/assets/Tasks/BOI/Day_1/minmaxtree/minmaxtree_en.pdf)”.** There is an unweighted tree with $N$ nodes, numbered $1 \dots N$. You need to assign a weight to each edge to make it a weighted tree. The weighted tree must satisfy $K$ conditions. There are two types of conditions: 1. $\ \texttt{M }x\ y\ z\ \ $ The maximum edge weight on the path from node $x$ to node $y$ is $z$. 2. $\ \texttt{m }x\ y\ z\ \ $ The minimum edge weight on the path from node $x$ to node $y$ is $z$. **It is guaranteed that the $z$ values in these $K$ conditions are all distinct.** Please construct such a tree and output the weight of each edge.

The first line contains an integer $N$. In the next $N - 1$ lines, each line contains two integers, indicating an edge connecting two nodes. Line $N + 1$ contains an integer $K$. In the next $K$ lines, each line starts with a letter $\texttt{M}$ or $\texttt{m}$, followed by three integers $x, y, z$.

Output $N - 1$ lines. Each line contains three integers $x, y, v$ separated by spaces, meaning an edge $(x, y)$ in the weighted tree has weight $v$.

Subtask #1 (7 points): $1 \le N, z \le 1000$. Subtask #2 (22 points): Only condition type 1, and no condition type 2. Subtask #3 (29 points): All paths from $x$ to $y$ given in condition type 1 are pairwise edge-disjoint. All paths from $x$ to $y$ given in condition type 2 are also pairwise edge-disjoint. Subtask #4 (42 points): No other restrictions. For all testdata, $1 \le N, K \le 70000$, $0 \le z \le 10^9$. Thanks to Planet6174 for providing the translation. Translated by ChatGPT 5