洛谷P4315 月下“毛景树”（边权维护）

毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。

爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有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 }