题目描述
毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。
爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有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个。
// luogu-judger-enable-o2 //妈的搞了两天终于搞出来了 //边权->点权 //每个点记录和他爸爸相连的那条边的权值 //对于修改和他爸爸相连的那条边的操作，视为对这个点的操作 //找第k条边：由于加的是双向边，所以第k条边是2*k和2*k+1，找两条边连接的深度小的那个点v就是第k条边 //所以，change操作就是单点修改 //cover就是区间修改 //add就是区间加 //max就是求区间最值 //lazy标记要分开记，因为 如果当前点有一个修改标记但是没下传，又来了个add操作，这时候，下边的点还没改 //但是add标记把lazy标记给覆盖了 //本来写的是俩标记，但是只是用来判断，用的addval做值的标记，但是一直WA //写成这样就A了，但是感觉好像一个样的东西啊。。。。 //如果当前点由cover标记，要让他的儿子的add标记=0 #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; const int N=1e5+5; const int INF=0x7fffffff; int n,m; int head[N],num_edge; struct Edge { int v,w,nxt; }edge[N<<1]; struct NODE { int fa,son; int dep,size; int s,t; int top; }node[N]; struct TREE { TREE *lson,*rson; int l,r,mid; int maxn,addval; int tag1,tag2; //tag1是add，tag2是cover }tree[N<<2]; typedef TREE* Tree; Tree Root,now_node=tree; inline int read() { char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f; } inline void add_edge(int u,int v,int w) { edge[++num_edge].v=v; edge[num_edge].w=w; edge[num_edge].nxt=head[u]; head[u]=num_edge; } int dfs1(int u) { node[u].size=1; for(int i=head[u],v;i;i=edge[i].nxt) { v=edge[i].v; if(v==node[u].fa) continue; node[v].fa=u; node[v].dep=node[u].dep+1; dfs1(v); node[u].size+=node[v].size; if(node[v].size>node[node[u].son].size) node[u].son=v; } } int bound; int dfs2(int u,int top) { node[u].top=top; node[u].s=++bound; if(node[u].son) { dfs2(node[u].son,top); for(int i=head[u],v;i;i=edge[i].nxt) { v=edge[i].v; if(v==node[u].son||v==node[u].fa) continue; dfs2(v,v); } } node[u].t=bound; } void build(Tree &root,int l,int r) { root=++now_node; root->l=l,root->r=r,root->mid=l+r>>1; root->tag2=-1; if(l==r) return; build(root->lson,l,root->mid); build(root->rson,root->mid+1,r); } inline void pushdown(const Tree &root) { if(root->tag2>=0) { root->lson->tag1=root->rson->tag1=0; root->lson->tag2=root->rson->tag2=root->tag2; root->lson->maxn=root->rson->maxn=root->tag2; root->tag2=-1; } if(root->tag1) { root->lson->maxn+=root->tag1; root->rson->maxn+=root->tag1; root->lson->tag1+=root->tag1; root->rson->tag1+=root->tag1; root->tag1=0; } } void change(const Tree &root,int l,int r,int w) { if(root->l==l&&root->r==r) { root->tag1=0; root->maxn=w; root->tag2=w; return; } pushdown(root); if(r<=root->mid) change(root->lson,l,r,w); else if(l>root->mid) change(root->rson,l,r,w); else { change(root->lson,l,root->mid,w); change(root->rson,root->mid+1,r,w); } root->maxn=max(root->lson->maxn,root->rson->maxn); } void add(const Tree &root,int l,int r,int w) { if(root->l==l&&root->r==r) { root->maxn+=w; root->tag1+=w; return; } pushdown(root); if(r<=root->mid) add(root->lson,l,r,w); else if(l>root->mid) add(root->rson,l,r,w); else { add(root->lson,l,root->mid,w); add(root->rson,root->mid+1,r,w); } root->maxn=max(root->lson->maxn,root->rson->maxn); } int query(const Tree &root,int l,int r) { if(root->l==l&&root->r==r) return root->maxn; pushdown(root); if(r<=root->mid) return query(root->lson,l,r); else if(l>root->mid) return query(root->rson,l,r); else return max(query(root->lson,l,root->mid),query(root->rson,root->mid+1,r)); } inline int Query(int x,int y) { int fx=node[x].top,fy=node[y].top; int ans=-INF; while(fx!=fy) { if(node[fx].dep>node[fy].dep) { ans=max(ans,query(Root,node[fx].s,node[x].s)); x=node[fx].fa; fx=node[x].top; } else { ans=max(ans,query(Root,node[fy].s,node[y].s)); y=node[fy].fa; fy=node[y].top; } } if(x==y) return ans; else if(node[x].dep>node[y].dep) return max(ans,query(Root,node[y].s+1,node[x].s)); else return max(ans,query(Root,node[x].s+1,node[y].s)); } inline void Add(int x,int y,int addval) { int fx=node[x].top,fy=node[y].top; while(fx!=fy) { if(node[fx].dep>node[fy].dep) { add(Root,node[fx].s,node[x].s,addval); x=node[fx].fa; fx=node[x].top; } else { add(Root,node[fy].s,node[y].s,addval); y=node[fy].fa; fy=node[y].top; } } if(x==y) return; else if(node[x].dep>node[y].dep) add(Root,node[y].s+1,node[x].s,addval); else add(Root,node[x].s+1,node[y].s,addval); } inline void Change(int x,int y,int w) { int fx=node[x].top,fy=node[y].top; while(fx!=fy) { if(node[fx].dep>node[fy].dep) { change(Root,node[fx].s,node[x].s,w); x=node[fx].fa; fx=node[x].top; } else { change(Root,node[fy].s,node[y].s,w); y=node[fy].fa; fy=node[y].top; } } if(x==y) return; else if(node[x].dep>node[y].dep) change(Root,node[y].s+1,node[x].s,w); else change(Root,node[x].s+1,node[y].s,w); } char s[10]; string A; int main() { n=read(); for(int i=1,u,v,w;i<n;++i) { u=read(),v=read(),w=read(); add_edge(u,v,w); add_edge(v,u,w); } dfs1(1); dfs2(1,1); build(Root,1,n); int a,b,c; for(int i=1;i<n;++i) { if(node[edge[i*2-1].v].dep>node[edge[i<<1].v].dep) a=edge[i*2-1].v; else a=edge[i<<1].v; change(Root,node[a].s,node[a].s,edge[i<<1].w); } while("why") { scanf("%s",s); if(s[0]=='S') break; if(s[0]=='M') { a=read(),b=read(); printf("%d ",Query(a,b)); } else if(s[0]=='A') { a=read(),b=read(),c=read(); Add(a,b,c); } else if(s[1]=='o') { a=read(),b=read(),c=read(); Change(a,b,c); } else { a=read(),b=read(); if(node[edge[a*2-1].v].dep>node[edge[a<<1].v].dep) a=edge[a*2-1].v; else a=edge[a<<1].v; change(Root,node[a].s,node[a].s,b); } } return 0; }