Qtree1

题目背景

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

题目描述

给定一棵n个节点的树,有两个操作: - CHANGE i ti 把第i条边的边权变成ti - QUERY a b 输出从a到b的路径中最大的边权,当a=b的时候,输出0

输入输出格式

输入格式


第一行输入一个n,表示节点个数 第二行到第n行每行输入三个数,ui,vi,wi,分别表示 ui,vi有一条边,边权是wi 第n+1行开始,一共有不定数量行,每一行分别有以下三种可能 CHANGE,QUERY同题意所述 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$ 操作次数 $\leq$ $3*10^5$ wi和ti $\leq$ $2^{31}-1$