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$ 互不相同。** 请构造出这棵树，并输出每条边的边权。

无

无

子任务 #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 提供的翻译