P4787 [BalkanOI 2018] Minmaxtree

**翻译自 [BalkanOI 2018](http://boi2018.ro) Day1 T3「[Minmaxtree](http://boi2018.ro/assets/Tasks/BOI/Day_1/minmaxtree/minmaxtree_en.pdf)」** 有一棵有 $N$ 个结点的无权树，结点分别编号为 $1\dots N$。现在要给每条边赋一个权值，使之变为一棵带权树。这棵带权树满足 $K$ 个条件，条件分为两类： 1. $\ \texttt{M }x\ y\ z\ \ $ 从结点 $x$ 到结点 $y$ 的链上最大的边权为 $z$； 2. $\ \texttt{m }x\ y\ z\ \ $ 从结点 $x$ 到结点 $y$ 的链上最小的边权为 $z$。 **保证这 $K$ 组条件的 $z$ 互不相同。** 请构造出这棵树，并输出每条边的边权。

第一行有一个整数 $N$。 在接下来的 $N-1$ 行中，每行两个整数，表示一条边连接的两个结点。 第 $N+1$ 行有一个整数 $K$。 在接下来的 $K$ 行中，每行开头有一个字母，字母为 $\texttt{M}$ 或 $\texttt{m}$，接下来有三个整数 $x, y, z$。

输出 $n-1$ 行，每行三个整数 $x, y, v$，用空格分隔，表示带权树的一条带权边。

子任务 #1（7 分）：$1 ≤ N, z ≤ 1000$； 子任务 #2（22 分）：只有条件 1，没有条件 2。 子任务 #3（29 分）：所有条件 1 中给出的 $x$ 到 $y$ 的链互不相交；所有条件 2 中给出的 $x$ 到 $y$ 的链也互不相交。 子任务 #4（42 分）：没有其他限制。 对于所有数据，$1 ≤ N, K ≤ 70000$，$0 ≤ z ≤ 10^9$。 感谢 Planet6174 提供的翻译