#P4787. [BalkanOI2018] Minmaxtree

[BalkanOI2018] Minmaxtree

题目描述

翻译自 BalkanOI 2018 Day1 T3「Minmaxtree

有一棵有 NN 个结点的无权树,结点分别编号为 1N1\dots N。现在要给每条边赋一个权值,使之变为一棵带权树。这棵带权树满足 KK 个条件,条件分为两类:

  1.  M x y z  \ \texttt{M }x\ y\ z\ \ 从结点 xx 到结点 yy 的链上最大的边权为 zz
  2.  m x y z  \ \texttt{m }x\ y\ z\ \ 从结点 xx 到结点 yy 的链上最小的边权为 zz

保证这 KK 组条件的 zz 互不相同。

请构造出这棵树,并输出每条边的边权。

输入格式

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

输出格式

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

4
1 2
2 3
3 4
3
M 1 2 1
m 1 4 0
M 2 3 100
3 2 100
1 2 1
4 3 0

提示

子任务 #1(7 分):1N,z10001 ≤ N, z ≤ 1000
子任务 #2(22 分):只有条件 1,没有条件 2。
子任务 #3(29 分):所有条件 1 中给出的 xxyy 的链互不相交;所有条件 2 中给出的 xxyy 的链也互不相交。
子任务 #4(42 分):没有其他限制。
对于所有数据,1N,K700001 ≤ N, K ≤ 700000z1090 ≤ z ≤ 10^9

感谢 Planet6174 提供的翻译