OI题库

【题目描述】

一天机房的夜晚，无数人在MC里奋斗着。。。

大家都知道矿产对于MC来说是多么的重要，但由于矿越挖越少，勇士们不得不跑到更远的地方挖矿，但这样路途上就会花费相当大的时间，导致挖矿效率底下。

cjj提议修一条铁路，大家一致同意。

大家都被CH分配了一些任务：

zjmfrank2012负责绘制出一个矿道地图，这个地图包括家（当然这也是一个矿，毕竟不把家掏空我们是不会走的），和无数个矿，所以大家应该可以想出这是一个无向无环图，也就是一棵树。

Digital_T和cstdio负责铺铁路。。所以这里没他们什么事，两位可以劳作去了。

这个时候song526210932和RMB突然发现有的矿道会刷怪，并且怪的数量会发生变化。作为采矿主力，他们想知道从一个矿到另一个矿的路上哪一段会最困难。。。（困难值用zjm的死亡次数表示）。

【输入格式】

输入文件的第一行有一个整数N，代表矿的数量。矿的编号是1到N。

接下来N-1行每行有三个整数a,b,c，代表第i号矿和第j号矿之间有一条路，在初始时这条路的困难值为c。

接下来有若干行，每行是“CHANGE i ti”或者“QUERY a b”，前者代表把第i条路（路按所给顺序从1到M编号）的困难值修改为ti，后者代表查询a到b所经过的道路中的最大困难值。

输入数据以一行“DONE”结束。

【输出格式】

对每个“QUERY”操作，输出一行一个正整数，即最大困难值。

【样例输入】

3

1 2 1

2 3 2

QUERY 1 2

CHANGE 1 3

QUERY 1 2

DONE

【样例输出】

1

3

【提示】

对于60%的数据，1<=N<=50

对于100%的数据，1<=N<=10000，1<=c<=1000000,1<=操作次数<=100000

【来源】

由GDFRWMY 改编自SPOJ 375 QTREE

数据by cstdio