题目描述
毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。
爬啊爬爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果 “毛景树”上有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个。
就是把边权给到边下面那个点之后就是树剖的板子题了。
线段树的两个lazy互相维护一下即可。
AC代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,u[N],v[N],w[N],vis[N];
int head[N],nex[N<<1],to[N<<1],tot;
int pos[N],bl[N],f[N],h[N],sz[N],son[N],cnt;
struct node{
int l,r,lazy,add,mx;
}t[N<<2];
inline void add(int a,int b){
to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
inline void push_up(int p){
t[p].mx=max(t[p<<1].mx,t[p<<1|1].mx);
}
inline void push_down(int p){
if(t[p].lazy){
t[p<<1].mx=t[p].lazy; t[p<<1|1].mx=t[p].lazy;
t[p<<1].add=t[p<<1|1].add=0;
t[p<<1].lazy=t[p].lazy; t[p<<1|1].lazy=t[p].lazy;
t[p].lazy=0;
}
if(t[p].add){
t[p<<1].add+=t[p].add; t[p<<1|1].add+=t[p].add;
t[p<<1].mx+=t[p].add; t[p<<1|1].mx+=t[p].add;
t[p].add=0;
}
}
void build(int p,int l,int r){
t[p].l=l; t[p].r=r;
if(l==r) return ; int mid=l+r>>1;
build(p<<1,l,mid); build(p<<1|1,mid+1,r);
}
void change(int p,int l,int r,int v){
if(t[p].l==l&&t[p].r==r){
t[p].mx=t[p].lazy=v; t[p].add=0; return ;
}
push_down(p); int mid=t[p].l+t[p].r>>1;
if(r<=mid) change(p<<1,l,r,v);
else if(l>mid) change(p<<1|1,l,r,v);
else change(p<<1,l,mid,v),change(p<<1|1,mid+1,r,v);
push_up(p);
}
void addsum(int p,int l,int r,int v){
if(t[p].l==l&&t[p].r==r){
t[p].mx+=v; t[p].add+=v; return ;
}
push_down(p); int mid=t[p].l+t[p].r>>1;
if(r<=mid) addsum(p<<1,l,r,v);
else if(l>mid) addsum(p<<1|1,l,r,v);
else addsum(p<<1,l,mid,v),addsum(p<<1|1,mid+1,r,v);
push_up(p);
}
int ask(int p,int l,int r){
if(t[p].l==l&&t[p].r==r) return t[p].mx;
push_down(p); int mid=t[p].l+t[p].r>>1;
if(r<=mid) return ask(p<<1,l,r);
else if(l>mid) return ask(p<<1|1,l,r);
else return max(ask(p<<1,l,mid),ask(p<<1|1,mid+1,r));
}
void dfs1(int x){
sz[x]=1;
for(int i=head[x];i;i=nex[i]){
if(f[x]==to[i]) continue;
f[to[i]]=x; h[to[i]]=h[x]+1;
dfs1(to[i]); sz[x]+=sz[to[i]];
if(sz[to[i]]>sz[son[x]]) son[x]=to[i];
}
}
void dfs2(int x,int belong){
pos[x]=++cnt; bl[x]=belong;
if(son[x]) dfs2(son[x],belong);
for(int i=head[x];i;i=nex[i])
if(h[to[i]]>h[x]&&to[i]!=son[x]) dfs2(to[i],to[i]);
}
void cover(int x,int y,int z){
while(bl[x]!=bl[y]){
if(h[bl[x]]<h[bl[y]]) swap(x,y);
change(1,pos[bl[x]],pos[x],z); x=f[bl[x]];
}
if(pos[x]==pos[y]) return ;
if(pos[x]>pos[y]) swap(x,y);
change(1,pos[x]+1,pos[y],z);
}
void updata(int x,int y,int z){
while(bl[x]!=bl[y]){
if(h[bl[x]]<h[bl[y]]) swap(x,y);
addsum(1,pos[bl[x]],pos[x],z); x=f[bl[x]];
}
if(pos[x]==pos[y]) return ;
if(pos[x]>pos[y]) swap(x,y);
addsum(1,pos[x]+1,pos[y],z);
}
int querymax(int x,int y){
int res=0;
while(bl[x]!=bl[y]){
if(h[bl[x]]<h[bl[y]]) swap(x,y);
res=max(res,ask(1,pos[bl[x]],pos[x])); x=f[bl[x]];
}
if(pos[x]==pos[y]) return res;
if(pos[x]>pos[y]) swap(x,y);
res=max(res,ask(1,pos[x]+1,pos[y]));
return res;
}
signed main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d %d %d",&u[i],&v[i],&w[i]);
add(u[i],v[i]); add(v[i],u[i]);
}
dfs1(1); dfs2(1,1); build(1,1,n);
for(int i=1;i<n;i++){
if(f[u[i]]==v[i]) vis[i]=u[i];
else vis[i]=v[i];
}
for(int i=1;i<n;i++) change(1,pos[vis[i]],pos[vis[i]],w[i]);
char op[10];
while(scanf("%s",op),op[0]!='S'){
int a,b,c; scanf("%d %d",&a,&b);
if(op[0]=='M') printf("%d\n",querymax(a,b));
else if(op[1]=='o') scanf("%d",&c),cover(a,b,c);
else if(op[0]=='A') scanf("%d",&c),updata(a,b,c);
else change(1,pos[vis[a]],pos[vis[a]],b);
}
return 0;
}
京公网安备 11010502036488号