~ “毛景树”上有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之间树枝上毛毛果个数最多有多少个。
输入格式
第一行一个正整数N。
接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。 接下来是操作和询问，以“Stop”结束。
输出格式
对于毛毛虫的每个询问操作，输出一个答案。
输入输出样例
输入 #1
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
输出 #1
9 16
说明/提示
1<=N<=100,000，操作+询问数目不超过100,000。
保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4
5 int n,x,y,v;
6 struct node{
7 int nxt,to,val,fro;
8 }edge[maxn*3];
9
10 struct node1{
11 int l,r,lazy1,lazy2;
12 ll sum,mx;
13 }tree[maxn*4];
14
15 int head[maxn],cnt;
16
17 void add(int x,int y,int v){
18 edge[++cnt].nxt=head[x];
19 edge[cnt].fro=x;
20 edge[cnt].to=y;
21 edge[cnt].val=v;
22 head[x]=cnt;
23 }
24
25 ll maxn(ll a,ll b){
26 return a>b?a:b;
27 }
28
29 int dep[maxn],fa[maxn],too[maxn],size[maxn],son[maxn],id[maxn],rev[maxn],w[maxn];
30 void dfs1(int x,int f){
31 fa[x]=f;
32 dep[x]=dep[f]+1;
33 size[x]=1;
34 int maxson=-1;
35 for(int i=head[x];i;i=edge[i].nxt){
36 int go=edge[i].to;
37 if(gp==fa[x]) continue;
38 w[go]=edge[i].val;
39 dfs1(go,x);
40 size[x]+=size[go];
41 if(size[go]>maxson){
42 maxson=size[go];
43 son[x]=go;
44 }
45 }
46 }
47
48 int Time;
49 void dfs2(int x,int topf){
50 top[x]=topf;
51 id[x]=++Time;
52 rev[id[x]]=w[x;
53 if(!son[x])] return;
54 dfs2(son[x],topf);
55 for(int i=head[x];i;i=edge[i].nxt){
56 int go=edge[i].to;
57 if(son[x]==go||go==fa[x]) continue;
58 dfs2(go,go);
59 }
60 }
61
62 void build(int now,int l,int r){
63 tree[now].l,tree[now].r=r,tree[now].lazy1=-1;tree[now].lazy2=0;
64 if(l==r){
65 tree[now].mx=rev[l];
66 return;
67 }
68 int mid=(l+r)/2;
69 build(now*2,l,mid);
70 build(now*2+1,mid+1,r);
71 tree[now].mx=max(tree[now*2].mx,tree[now*2+1].mx);
72 }
73
74 void pushdown(int now){
75 if(tree[now].lazy1!=-1){
76 tree[now].mx=tree[now].lazy1;
77 tree[now].mx=tree[now].lazy1;
78 tree[now*2].la
79 }
80 }