树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！树剖！
练习情况:
以上都是维护节点的树剖，本质都是一个东西。
树剖
将整颗树，剖分成轻重链，再用数据结构维护。
操作主要是
-
1 x y z，表示将树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值都加上 \(z\)。 -
2 x y，表示求树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值之和。 -
3 x z，表示将以 \(x\) 为根节点的子树内所有节点值都加上 \(z\)。 -
4 x表示求以 \(x\) 为根节点的子树内所有节点值之和。
数据结构维护的一般是节点的 dfs 序。
对于最短路径上的操作，我们要用类似 LCA 的方法跳链，对路径上的链进行操作。
对于子树的操作，因为 dfs 序是连续的，所以可以直接进行维护。
Code:
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define Ld long double
#define l(p) tree[p].l
#define r(p) tree[p].r
#define sum(p) tree[p].sum
#define add(p) tree[p].add
const int N = 100005,M=100005;
LL n,m,r,mod,a[N];
LL head[N],net[M*2],val[M*2],idx=1;
LL f[N],d[N],son[N],id[N],siz[N],rk[N],tp[N],cnt;
LL op,x,y,z;
struct Segment_tree{
LL sum,add,l,r;
}tree[N*4];
inline char readc(){
char ch=getchar();
while(!((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))) ch=getchar();
return ch;
}
inline LL read(){
LL s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
return s*w;
}
inline void print(LL x){
char F[200];LL cnt=0;
if(x==0){putchar('0');putchar('\n');return ;}
if(x<0){putchar('-');x=-x;}
while(x){F[++cnt]=x%10;x/=10;}
while(cnt) putchar(F[cnt--]+'0');
putchar('\n');return ;
}
void add1(LL x,LL y){
val[++idx]=y;
net[idx]=head[x];
head[x]=idx;
return ;
}
void dfs1(LL u,LL fa){
f[u]=fa,d[u]=d[fa]+1,siz[u]=1;
for(int i=head[u];i;i=net[i]){
LL v=val[i];
if(v==fa) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
return ;
}
void dfs2(LL u,LL top){
tp[u]=top,id[u]=++cnt,rk[cnt]=u;
if(son[u]) dfs2(son[u],top);
for(int i=head[u];i;i=net[i]){
LL v=val[i];
if(v!=f[u]&&v!=son[u])
dfs2(v,v);
}
return ;
}
void pushup(LL p){
sum(p)=(sum(p<<1)+sum(p<<1|1))%mod;
return ;
}
void pushdown(LL p){
if(!add(p)) return ;
add(p<<1)=(add(p<<1)+add(p))%mod;
add(p<<1|1)=(add(p<<1|1)+add(p))%mod;
sum(p<<1)=(sum(p<<1)+add(p)*(r(p<<1)-l(p<<1)+1))%mod;
sum(p<<1|1)=(sum(p<<1|1)+add(p)*(r(p<<1|1)-l(p<<1|1)+1))%mod;
add(p)=0;
return ;
}
void build(LL p,LL l,LL r){
l(p)=l,r(p)=r;
if(l==r){
sum(p)=a[rk[l]];
return ;
}
LL mid=(l(p)+r(p))>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void change2(LL p,LL l,LL r,LL k){
if(l(p)>=l&&r(p)<=r){
add(p)=(add(p)+k)%mod;
sum(p)=(sum(p)+k*(r(p)-l(p)+1))%mod;
return ;
}
pushdown(p);
LL mid=(l(p)+r(p))>>1;
if(l<=mid) change2(p<<1,l,r,k);
if(r>mid) change2(p<<1|1,l,r,k);
pushup(p);
return ;
}
void change1(LL p,LL l,LL r,LL k){
while(tp[l]!=tp[r]){
if(d[tp[l]]<d[tp[r]]) swap(l,r);
change2(1,id[tp[l]],id[l],k);
l=f[tp[l]];
}
if(id[l]>id[r]) swap(l,r);
change2(1,id[l],id[r],k);
return ;
}
LL query2(LL p,LL l,LL r){
if(l(p)>=l&&r(p)<=r) return sum(p);
pushdown(p);
LL mid=(l(p)+r(p))>>1,val=0;
if(l<=mid) val+=query2(p<<1,l,r);
if(r>mid) val+=query2(p<<1|1,l,r);
return val%mod;
}
LL query1(LL p,LL l,LL r){
LL val=0;
while(tp[l]!=tp[r]){
if(d[tp[l]]<d[tp[r]]) swap(l,r);
val=(val+query2(1,id[tp[l]],id[l]))%mod;
l=f[tp[l]];
}
if(id[l]>id[r]) swap(l,r);
return (val+query2(1,id[l],id[r]))%mod;
}
int main(){
n=read(),m=read(),r=read(),mod=read();
for(int i=1;i<=n;i++) a[i]=read();
for(LL i=1,u,v;i<n;i++){
u=read(),v=read();
add1(u,v);
add1(v,u);
}
dfs1(r,0);
dfs2(r,r);
build(1,1,n);
for(int i=1;i<=m;i++){
op=read(),x=read();
if(op==1){
y=read(),z=read();
change1(1,x,y,z);
}else
if(op==2){
y=read();
print(query1(1,x,y));
}else
if(op==3){
z=read();
change2(1,id[x],id[x]+siz[x]-1,z);
}else
if(op==4){
print(query2(1,id[x],id[x]+siz[x]-1));
}
}
return 0;
}
P3038 [USACO11DEC]Grass Planting G
以上是维护边的树剖。
这个相对于维护点的树剖只有一点点差别。
我们将每条边的权值赋给边两端深度较大的那个节点。
差别
在两点之间维护时
if(id[l]>id[r]) swap(l,r);
return max(val,query2(1,id[l]+1,id[r]));
id[l] 为 LCA 这个节点的权值不包含在要维护的边内，所以要加 1 。
Code:
一天写了挺多树剖的，但这些都感觉长的差不多，只是把序列拍在树上，增加1kb码量。
那么将线段树的题目搞到树上是不是就是一道新的树剖。
标签：26,ch,树剖,LL,节点,&&,2022.10,id From： https://www.cnblogs.com/xingke233/p/18492627