5987 - NOI：树链剖分：树路径最大边权

给定一棵 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 \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。