月下“毛景树”

Time Limit:20000MS  Memory Limit:65536K
Total Submit:77 Accepted:15
Case Time Limit:2000MS

Description

毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。
毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着 他最爱吃的毛毛果~~~
“毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛 毛果的个数：
 Change k w：将第k条树枝上毛毛果的个数改变为w个。
 Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。
 Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。
由于毛毛虫很贪，于是他会有如下询问：
 Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

Input

第一行一个正整数N。
接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。
接下来是操作和询问，以“Stop”结束。

Output

对于毛毛虫的每个询问操作，输出一个答案。

Sample Input

4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop

Sample Output

9
16

【Data Range】
1<=N<=100,000，操作+询问数目不超过100,000。
保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。

Source

绍兴一中
没什么好说的。裸的树链剖分。。为了战胜TLE我搞的累死。。最后发现几处地方写错了。。囧。。。线段树维护的时候维护两个标记Add和Same具体操作看代码吧囧。。
我这个干脆就给每个线段树开了个内存池然后变成纯数组了。。。。非常的猥琐。。
Code：
www.ideone.com/oEXcP