[SPOJ QTREE]难存的情缘

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file qtree.in Output file qtree.out

【题目描述】

一天机房的夜晚,无数人在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