该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P4114 Qtree1

题目描述

给定一棵 $n$ 个节点的树，有两种操作：

• CHANGE i t 把第 $i$ 条边的边权变成 $t$
• QUERY a b 输出从 $a$ 到 $b$ 的路径上最大的边权。当 $a=b$ 时，输出 $0$

输入格式

第一行是一个整数 $n$，表示节点个数。
第二行到第 $n$ 行每行输入三个整数 $u,v,w$ ，分别表示 $u$ 与 $v$ 有一条边，边权是 $w$。
第 $n+1$ 行开始，一共有不定数量行，每一行先包含一个字符串，分别有以下三种可能：

• CHANGE 接下来包含两个整数 $x, t$ ，表示一次修改操作。
• QUERY 接下来包含两个正整数 $a, b$ ， 表示一次查询操作。
• DONE 表示输入结束。

输出格式

对于每个 QUERY 操作，输出一行一个数，表示 $a,b$ 的路径上最大的边权。

输入输出样例 #1

输入 #1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

输出 #1

1
3

说明/提示

数据规模与约定

对于全部的测试点，保证：

• $1 \leq n \leq 10^6$。
• $1 \leq u, v, a, b \leq n$，$1 \leq x < n$。
• $1 \leq w, t \leq 2^{31} - 1$。
• 操作次数不大于 $10^5$。