Qtree1

题目背景

**数据规模和 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$ 的路径上最大的边权。

输入输出样例

输入样例 #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^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$。