题目背景

数据规模和 spoj 上有所不同。

题目描述

给定一棵 $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$ 的路径上最大的边权。

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

1
3

提示

数据规模与约定

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

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