P4315 月下“毛景树”（树剖模板）

月下毛景树

好久没到树剖了,还好一遍过了…

边权转点权就是把边的权值下放到深度较大的那个点

然后在树上区间修改的时候,是不能算$lca$的

而当$x,y$跳到一条链的时候就是$lca$

所以最后一次是$update(id[x]+1,id[y])$

另外这里有覆盖操作和区间加操作

覆盖操作优先级最高,注意一下$push\_down$写法

void push_down(int rt,int l,int r) { if( laz1[rt]!=-1 )//先改变 { laz2[ls] = laz2[rs] = 0;//清空儿子 laz1[ls]=laz1[rs]=a[ls]=a[rs]=laz1[rt];//覆盖 laz1[rt]=-1; } laz2[ls]+=laz2[rt], laz2[rs]+=laz2[rt]; a[ls]+=laz2[rt], a[rs]+=laz2[rt]; laz2[rt] = 0; }

然后涉及到区间覆盖操作时

直接清空操作二的标记即可

#include <bits/stdc++.h> using namespace std; #define ls (rt<<1) #define rs (rt<<1|1) #define mid (l+r>>1) #define lson ls,l,mid #define rson rs,mid+1,r const int maxn=2e5+10; int uu[maxn],vv[maxn],son[maxn],n; struct edge{ int to,nxt,w; }d[maxn]; int head[maxn],cnt=1; void add(int u,int v,int w){d[++cnt] = (edge){v,head[u],w},head[u]=cnt;} int siz[maxn],fa[maxn],deep[maxn],wt[maxn]; void dfs1(int u,int father) { siz[u]=1,fa[u]=father,deep[u]=deep[father]+1; for(int i=head[u];i;i=d[i].nxt ) { int v=d[i].to; if( v==father ) continue; wt[v]=d[i].w; dfs1(v,u); siz[u]+=siz[v]; if( siz[son[u]]<siz[v] ) son[u]=v; } } int id[maxn],top[maxn],w[maxn],num; void dfs2(int u,int topf) { id[u]=++num, top[u]=topf, w[num]=wt[u]; if( son[u] ) dfs2(son[u],topf); for(int i=head[u];i;i=d[i].nxt ) { int v=d[i].to; if( v==fa[u] || v==son[u] ) continue; dfs2(v,v); } } int laz1[maxn<<2],laz2[maxn<<2],a[maxn<<2];//直接改变,添加 void build(int rt,int l,int r) { laz1[rt] = -1,laz2[rt] = 0; if( l==r ) { a[rt]=w[l]; return; } build(lson); build(rson); a[rt] = max( a[ls],a[rs] ); } void push_down(int rt,int l,int r) { if( laz1[rt]!=-1 )//先改变 { laz2[ls] = laz2[rs] = 0; laz1[ls]=laz1[rs]=a[ls]=a[rs]=laz1[rt]; laz1[rt]=-1; } laz2[ls]+=laz2[rt], laz2[rs]+=laz2[rt]; a[ls]+=laz2[rt], a[rs]+=laz2[rt]; laz2[rt] = 0; } void update(int rt,int l,int r,int L,int R,int val,int type) { if( l>=L&&r<=R ) { if( type==1 ) laz1[rt] = a[rt] = val, laz2[rt]=0;//直接改变 else laz2[rt]+=val,a[rt]+=val; return; } if( r<L||l>R ) return; push_down(rt,l,r); update(lson,L,R,val,type); update(rson,L,R,val,type); a[rt] = max( a[ls],a[rs] ); } int ask(int rt,int l,int r,int L,int R) { if( l>=L&&r<=R ) return a[rt]; if( l>R||r<L ) return 0; push_down(rt,l,r); return max( ask(lson,L,R),ask(rson,L,R) ); } void modify(int x,int y,int val,int type) { while( top[x]!=top[y] ) { if( deep[top[x]]<deep[top[y]] ) swap(x,y); update(1,1,n,id[top[x]],id[x],val,type); x = fa[top[x]]; } if( deep[x]>deep[y] ) swap(x,y); update(1,1,n,id[x]+1,id[y],val,type); } int askmax(int x,int y) { int ans=0; while( top[x]!=top[y] ) { if( deep[top[x]]<deep[top[y]] ) swap(x,y); ans = max( ans,ask(1,1,n,id[top[x]],id[x]) ); x=fa[top[x]]; } if( deep[x]>deep[y] ) swap(x,y); ans = max( ans,ask(1,1,n,id[x]+1,id[y] )); return ans; } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int w; scanf("%d%d%d",&uu[i],&vv[i],&w); add(uu[i],vv[i],w); add(vv[i],uu[i],w); } dfs1(1,0); dfs2(1,1); build(1,1,n); for(int i=1;i<n;i++) if( deep[vv[i]]>deep[uu[i]] ) swap(uu[i],vv[i] ); string type; while( cin >> type && type!="Stop" ) { int u,v,w; scanf("%d%d",&u,&v); if( type == "Change" ) { modify(uu[u],vv[u],v,1); // update( 1,1,n,id[uu[u]],id[uu[u]],v,1 ); } else if( type=="Cover" ) { scanf("%d",&w); modify(u,v,w,1); } else if( type=="Add" ) { scanf("%d",&w); modify(u,v,w,2); } else printf("%d\n",askmax(u,v)); } }