#2712. 「BalkanOI 2018 Day1」Minmaxtree

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

翻译自 BalkanOI 2018 Day1 T3「Minmaxtree

有一棵有 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 ,用空格分隔,表示带权树的一条带权边。

样例

样例输入

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 分): 1 ≤ N, z ≤ 1000
子任务 #2(22 分):只有条件 1,没有条件 2。
子任务 #3(29 分):所有条件 1 中给出的 x y 的链互不相交;所有条件 2 中给出的 x y 的链也互不相交。
子任务 #4(42 分):没有其他限制。
对于所有数据, 1 ≤ N, K ≤ 70000, 1 ≤ z ≤ 10^9


感谢 applese 提供 SPJ。