现在你有一棵树,共有 n(n ≤ 100000)个结点,由 1 至 n 依次编号。有 n – 1 条边,每条边有一个权值,由 1 至 n – 1 依次编号。现在你要完成一些指令,这些指令包括: CHANGE i v,表示将第 i 条边的权值改为 v; QUERY a b,表示将结点 a 到结点 b 路径上的最大权值输出。
第一个为一个整数 m,表示有 m 组数据。 第二行为一个整数 n,表示结点个数。 接下来 n – 1 行分别有 3 个整数,分别表示该条边的结点编号和权值。 然后是若干条指令要求(不超过 3 × 10^5),指令格式见上文说明,最后以 “DONE” 结束。
对于每个查询指令,输出答案一行。
3 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE
1 3