题目描述
毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。
爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有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）处理边权类的树剖的时候要在修改和查询的时候避开LCA，详细见代码。
（2）在线段树维护两个以上的lazy标记的时候要严格注意传递的顺序，这个不能写错，这道题的spread函数是重点。
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+100; int n,m; struct e { int u,v,w,nxt,e_id; }edge[maxn*2]; int head[maxn]; int tot; void addedge (int u,int v,int w,int e_id) { edge[tot].u=u; edge[tot].v=v; edge[tot].w=w; edge[tot].e_id=e_id; edge[tot].nxt=head[u]; head[u]=tot++; edge[tot].u=v; edge[tot].v=u; edge[tot].w=w; edge[tot].e_id=e_id; edge[tot].nxt=head[v]; head[v]=tot++; } int belong[maxn];//记录每条边的儿子节点 int son[maxn]; int id[maxn]; int fa[maxn]; int cnt; int dep[maxn]; int size[maxn]; int top[maxn]; int w[maxn]; int wt[maxn]; struct node { int l,r; int sum; int lazy1; int lazy2=-1; }segTree[maxn*4]; void build (int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; if (l==r) { segTree[i].sum=wt[l]; return; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); segTree[i].sum=max(segTree[i<<1].sum,segTree[i<<1|1].sum); } void spread (int i) { if (segTree[i].lazy2>=0) { segTree[i<<1].sum=segTree[i].lazy2; segTree[i<<1|1].sum=segTree[i].lazy2; segTree[i<<1].lazy2=segTree[i].lazy2; segTree[i<<1|1].lazy2=segTree[i].lazy2; segTree[i].lazy2=-1; segTree[i<<1].lazy1=0; segTree[i<<1|1].lazy1=0; } if (segTree[i].lazy1) { segTree[i<<1].sum+=segTree[i].lazy1; segTree[i<<1|1].sum+=segTree[i].lazy1; segTree[i<<1].lazy1+=segTree[i].lazy1; segTree[i<<1|1].lazy1+=segTree[i].lazy1; segTree[i].lazy1=0; } } void update (int i,int l,int r,int val,int f) { if (l<=segTree[i].l&&segTree[i].r<=r) { if (f==1) { segTree[i].sum+=val; segTree[i].lazy1+=val; return; } else { segTree[i].sum=val; segTree[i].lazy2=val; segTree[i].lazy1=0; return; } } spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; if (l<=mid) update(i<<1,l,r,val,f); if (r>mid) update(i<<1|1,l,r,val,f); segTree[i].sum=max(segTree[i<<1].sum,segTree[i<<1|1].sum); } int query (int i,int l,int r) { if (l<=segTree[i].l&&r>=segTree[i].r) return segTree[i].sum; spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; int ans=0; if (l<=mid) ans=max(ans,query(i<<1,l,r)); if (r>mid) ans=max(ans,query(i<<1|1,l,r)); return ans; } int qRange (int x,int y) { int ans=0; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans=max(ans,query(1,id[top[x]],id[x])); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); ans=max(ans,query(1,id[x]+1,id[y])); return ans; } void upRange (int x,int y,int k,int f) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); update(1,id[top[x]],id[x],k,f); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); update(1,id[x]+1,id[y],k,f); } int lca (int x,int y) { for (;top[x]!=top[y];dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]]); return dep[x]<dep[y]?x:y; } void dfs1 (int x,int f,int deep) { dep[x]=deep; fa[x]=f; size[x]=1; int maxson=-1; for (int i=head[x];i!=-1;i=edge[i].nxt) { int y=edge[i].v; if (y==f) continue; belong[edge[i].e_id]=y; w[y]=edge[i].w; dfs1(y,x,deep+1); size[x]+=size[y]; if (size[y]>maxson) son[x]=y,maxson=size[y]; } } void dfs2 (int x,int topf) { id[x]=++cnt; wt[cnt]=w[x]; top[x]=topf; if (!son[x]) return; dfs2(son[x],topf); for (int i=head[x];i!=-1;i=edge[i].nxt) { int y=edge[i].v; if (y==fa[x]||y==son[x]) continue; dfs2(y,y); } } int main () { scanf("%d",&n); for (int i=0;i<=n;i++) head[i]=-1; for (int i=1;i<n;i++) { int x,y,w; scanf("%d%d%d",&x,&y,&w); addedge(x,y,w,i); } dfs1(1,0,1); dfs2(1,1); build(1,1,n); while (1) { string s; cin>>s; if (s=="Stop") break; if (s=="Change") { int k,w; scanf("%d%d",&k,&w); update(1,id[belong[k]],id[belong[k]],w,2); } else if (s=="Cover") { int u,v,w; scanf("%d%d%d",&u,&v,&w); upRange(u,v,w,2); } else if (s=="Add") { int u,v,w; scanf("%d%d%d",&u,&v,&w); upRange(u,v,w,1); } else if (s=="Max"){ int u,v; scanf("%d%d",&u,&v); printf("%d ",qRange(u,v)); } } }