开始复习(NOIP)啦！
树链剖分是一种非常实用的算法，树的重链最多只有(logn)条，所以它的复杂度是(O(nlogn))
如果树再套上一个线段树，那么复杂度多乘一个(logn)
那么线段树怎么表示区间呢？可以用(dfs)序修改，多开一个(id[i])表示(i)节点在线段树的位置
我们记录一个节点的深度(dep[i])，链首数组(top[i])，重儿子(son[i])，父亲(fa[i])，一个子树的大小(siz[i])
然后就可以愉快的解决掉【模板】树链剖分
(Code Below:)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100000+10;
ll n,m,r,p;
ll sum[maxn<<2],lazy[maxn<<2],a[maxn];
ll head[maxn],from[maxn<<1],to[maxn<<1],tot;
ll top[maxn],id[maxn],dep[maxn],son[maxn],siz[maxn],mp[maxn],fa[maxn],tim;
void add(ll x,ll y){
to[++tot]=y;
from[tot]=head[x];
head[x]=tot;
}
void pushup(ll rt){sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%p;}
void pushdown(ll rt,ll len){
if(lazy[rt]){
sum[rt<<1]=(sum[rt<<1]+lazy[rt]*(len-(len>>1)))%p;
sum[rt<<1|1]=(sum[rt<<1|1]+lazy[rt]*(len>>1))%p;
lazy[rt<<1]=(lazy[rt<<1]+lazy[rt])%p;
lazy[rt<<1|1]=(lazy[rt<<1|1]+lazy[rt])%p;
lazy[rt]=0;
}
}
void build(ll l,ll r,ll rt){
if(l==r){
sum[rt]=mp[l]%p;
return;
}
ll mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void update(ll L,ll R,ll C,ll l,ll r,ll rt){
if(L<=l&&r<=R){
sum[rt]=(sum[rt]+(r-l+1)*C)%p;
lazy[rt]=(lazy[rt]+C)%p;
return;
}
ll mid=(l+r)>>1;
pushdown(rt,r-l+1);
if(L<=mid) update(L,R,C,l,mid,rt<<1);
if(R>mid) update(L,R,C,mid+1,r,rt<<1|1);
pushup(rt);
}
ll query(ll L,ll R,ll l,ll r,ll rt){
if(L<=l&&r<=R) return sum[rt];
ll mid=(l+r)>>1,ans=0;
pushdown(rt,r-l+1);
if(L<=mid) ans=(ans+query(L,R,l,mid,rt<<1))%p;
if(R>mid) ans=(ans+query(L,R,mid+1,r,rt<<1|1))%p;
return ans;
}
void dfs1(ll x,ll f,ll deep){
dep[x]=deep;
fa[x]=f;
siz[x]=1;
ll maxson=-1;
for(ll i=head[x];i;i=from[i]){
ll y=to[i];
if(y==f) continue;
dfs1(y,x,deep+1);
siz[x]+=siz[y];
if(siz[y]>maxson){
son[x]=y;
maxson=siz[y];
}
}
}
void dfs2(ll x,ll f){
id[x]=++tim;
top[x]=f;
mp[tim]=a[x];
if(son[x]) dfs2(son[x],f);
for(ll i=head[x];i;i=from[i]){
ll y=to[i];
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
int main()
{
scanf("%lld%lld%lld%lld",&n,&m,&r,&p);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(ll i=1;i<n;i++){
ll x,y;
scanf("%lld%lld",&x,&y);
add(x,y);add(y,x);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,n,1);
for(ll i=1;i<=m;i++){
ll op,x,y,z;
scanf("%lld",&op);
if(op==1){
scanf("%lld%lld%lld",&x,&y,&z);
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
update(id[top[x]],id[x],z,1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(id[x],id[y],z,1,n,1);
}
if(op==2){
scanf("%lld%lld",&x,&y);
ll ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans=(ans+query(id[top[x]],id[x],1,n,1))%p;
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans=(ans+query(id[x],id[y],1,n,1))%p;
printf("%lld
",ans%p);
}
if(op==3){
scanf("%lld%lld",&x,&z);
update(id[x],id[x]+siz[x]-1,z,1,n,1);
}
if(op==4){
scanf("%lld",&x);
printf("%lld
",query(id[x],id[x]+siz[x]-1,1,n,1)%p);
}
}
return 0;
}
[ZJOI2008]树的统计
其实就是开两个线段树，一个维护最大值，一个维护权值和，一道考验码力的题
(Code Below:)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100000+10;
const ll inf=-100000;
ll n,m;
ll sum[maxn<<2],sumv[maxn<<2],lazy[maxn<<2],lazyv[maxn<<2],a[maxn];
ll head[maxn],to[maxn<<1],nxt[maxn<<1],tot;
ll dep[maxn],top[maxn],son[maxn],siz[maxn],fa[maxn],id[maxn],mp[maxn],tim;
void add(ll x,ll y){
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs1(ll x,ll f,ll deep){
dep[x]=deep;
fa[x]=f;
siz[x]=1;
int maxson=-1;
for(ll i=head[x];i;i=nxt[i]){
ll y=to[i];
if(y==f) continue;
dfs1(y,x,deep+1);
siz[x]+=siz[y];
if(siz[y]>maxson){
son[x]=y;
maxson=siz[y];
}
}
}
void dfs2(ll x,ll f){
id[x]=++tim;
mp[tim]=a[x];
top[x]=f;
if(son[x]) dfs2(son[x],f);
for(ll i=head[x];i;i=nxt[i]){
ll y=to[i];
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
void pushup(ll rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
sumv[rt]=max(sumv[rt<<1],sumv[rt<<1|1]);
}
void pushdown(ll rt,ll len){
if(lazy[rt]){
lazy[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
sum[rt<<1]+=lazy[rt]*(len-(len>>1));
sum[rt<<1|1]+=lazy[rt]*(len>>1);
lazy[rt]=0;
}
if(lazyv[rt]){
lazyv[rt<<1]=lazyv[rt];
lazyv[rt<<1|1]=lazyv[rt];
sumv[rt]=lazyv[rt];
sumv[rt]=lazyv[rt];
lazyv[rt]=0;
}
}
void build(ll l,ll r,ll rt){
if(l==r){
sum[rt]=sumv[rt]=mp[l];
return;
}
ll mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void update(ll L,ll C,ll l,ll r,ll rt){
if(l==L&&r==L){
sum[rt]=sumv[rt]=C;
lazy[rt]+=C;lazyv[rt]=C;
return;
}
ll mid=(l+r)>>1;
pushdown(rt,r-l+1);
if(L<=mid) update(L,C,l,mid,rt<<1);
if(L>mid) update(L,C,mid+1,r,rt<<1|1);
pushup(rt);
}
ll queryM(ll L,ll R,ll l,ll r,ll rt){
if(L<=l&&r<=R) return sumv[rt];
ll mid=(l+r)>>1,ans=inf;
pushdown(rt,r-l+1);
if(L<=mid) ans=max(ans,queryM(L,R,l,mid,rt<<1));
if(R>mid) ans=max(ans,queryM(L,R,mid+1,r,rt<<1|1));
return ans;
}
ll queryS(ll L,ll R,ll l,ll r,ll rt){
if(L<=l&&r<=R) return sum[rt];
ll mid=(l+r)>>1,ans=0;
pushdown(rt,r-l+1);
if(L<=mid) ans+=queryS(L,R,l,mid,rt<<1);
if(R>mid) ans+=queryS(L,R,mid+1,r,rt<<1|1);
return ans;
}
int main()
{
scanf("%lld",&n);
for(ll i=1;i<n;i++){
ll x,y;
scanf("%lld%lld",&x,&y);
add(x,y);add(y,x);
}
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
scanf("%lld",&m);
dfs1(1,0,1);
dfs2(1,1);
build(1,n,1);
for(ll i=1;i<=m;i++){
char op[10];ll x,y;
scanf("%s%lld%lld",&op,&x,&y);
if(op[0]=='C'){
update(id[x],y,1,n,1);
}
else if(op[0]=='Q'&&op[1]=='M'){
ll ans=inf;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans=max(ans,queryM(id[top[x]],id[x],1,n,1));
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans=max(ans,queryM(id[x],id[y],1,n,1));
printf("%lld
",ans);
}
else {
ll ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=queryS(id[top[x]],id[x],1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=queryS(id[x],id[y],1,n,1);
printf("%lld
",ans);
}
}
return 0;
}
[HAOI2015]树上操作
太特殊了吧，直接暴力都行啊
但是上树剖更快(qwq)
(Code Below:)
// luogu-judger-enable-o2
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100000+10;
ll n,m,r,p;
ll sum[maxn<<2],lazy[maxn<<2],a[maxn];
ll head[maxn],from[maxn<<1],to[maxn<<1],tot;
ll top[maxn],id[maxn],dep[maxn],son[maxn],siz[maxn],mp[maxn],fa[maxn],tim;
void add(ll x,ll y){
to[++tot]=y;
from[tot]=head[x];
head[x]=tot;
}
void pushup(ll rt){sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%p;}
void pushdown(ll rt,ll len){
if(lazy[rt]){
sum[rt<<1]=(sum[rt<<1]+lazy[rt]*(len-(len>>1)))%p;
sum[rt<<1|1]=(sum[rt<<1|1]+lazy[rt]*(len>>1))%p;
lazy[rt<<1]=(lazy[rt<<1]+lazy[rt])%p;
lazy[rt<<1|1]=(lazy[rt<<1|1]+lazy[rt])%p;
lazy[rt]=0;
}
}
void build(ll l,ll r,ll rt){
if(l==r){
sum[rt]=mp[l]%p;
return;
}
ll mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void update(ll L,ll R,ll C,ll l,ll r,ll rt){
if(L<=l&&r<=R){
sum[rt]=(sum[rt]+(r-l+1)*C)%p;
lazy[rt]=(lazy[rt]+C)%p;
return;
}
ll mid=(l+r)>>1;
pushdown(rt,r-l+1);
if(L<=mid) update(L,R,C,l,mid,rt<<1);
if(R>mid) update(L,R,C,mid+1,r,rt<<1|1);
pushup(rt);
}
ll query(ll L,ll R,ll l,ll r,ll rt){
if(L<=l&&r<=R) return sum[rt];
ll mid=(l+r)>>1,ans=0;
pushdown(rt,r-l+1);
if(L<=mid) ans=(ans+query(L,R,l,mid,rt<<1))%p;
if(R>mid) ans=(ans+query(L,R,mid+1,r,rt<<1|1))%p;
return ans;
}
void dfs1(ll x,ll f,ll deep){
dep[x]=deep;
fa[x]=f;
siz[x]=1;
ll maxson=-1;
for(ll i=head[x];i;i=from[i]){
ll y=to[i];
if(y==f) continue;
dfs1(y,x,deep+1);
siz[x]+=siz[y];
if(siz[y]>maxson){
son[x]=y;
maxson=siz[y];
}
}
}
void dfs2(ll x,ll f){
id[x]=++tim;
top[x]=f;
mp[tim]=a[x];
if(son[x]) dfs2(son[x],f);
for(ll i=head[x];i;i=from[i]){
ll y=to[i];
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
int main()
{
scanf("%lld%lld",&n,&m);r=1;p=1e15;
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(ll i=1;i<n;i++){
ll x,y;
scanf("%lld%lld",&x,&y);
add(x,y);add(y,x);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,n,1);
for(ll i=1;i<=m;i++){
ll op,x,y,z;
scanf("%lld",&op);
if(op==1){
scanf("%lld%lld",&x,&z);
y=x;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
update(id[top[x]],id[x],z,1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(id[x],id[y],z,1,n,1);
}
if(op==2){
scanf("%lld%lld",&x,&z);
update(id[x],id[x]+siz[x]-1,z,1,n,1);
}
if(op==3){
scanf("%lld",&x);
ll ans=0;y=1;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans=(ans+query(id[top[x]],id[x],1,n,1))%p;
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans=(ans+query(id[x],id[y],1,n,1))%p;
printf("%lld
",ans);
}
}
return 0;
}
[NOI2015]软件包管理器
解释操作：
1、安装操作：先查询(i)节点到根节点的和，将(i)节点到根节点的值从(0)改成(1)
2、卸载操作：先查询(i)节点子树的和，再修改(i)节点子树的值从(1)改成(0)
那么直接上裸的树剖就好吧
(Code Below:)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100000+10;
ll n,m,r,p;
ll sum[maxn<<2],lazy[maxn<<2],a[maxn];
ll head[maxn],from[maxn<<1],to[maxn<<1],tot;
ll top[maxn],id[maxn],dep[maxn],son[maxn],siz[maxn],mp[maxn],fa[maxn],tim;
void add(ll x,ll y){
to[++tot]=y;
from[tot]=head[x];
head[x]=tot;
}
void pushup(ll rt){sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%p;}
void pushdown(ll rt,ll len){
if(lazy[rt]!=-1){
sum[rt<<1]=lazy[rt]*(len-(len>>1))%p;
sum[rt<<1|1]=lazy[rt]*(len>>1)%p;
lazy[rt<<1]=lazy[rt]%p;
lazy[rt<<1|1]=lazy[rt]%p;
lazy[rt]=-1;
}
}
void build(ll l,ll r,ll rt){
if(l==r){
sum[rt]=mp[l]%p;
return;
}
ll mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void update(ll L,ll R,ll C,ll l,ll r,ll rt){
if(L<=l&&r<=R){
sum[rt]=(r-l+1)*C%p;
lazy[rt]=C%p;
return;
}
ll mid=(l+r)>>1;
pushdown(rt,r-l+1);
if(L<=mid) update(L,R,C,l,mid,rt<<1);
if(R>mid) update(L,R,C,mid+1,r,rt<<1|1);
pushup(rt);
}
ll query(ll L,ll R,ll l,ll r,ll rt){
if(L<=l&&r<=R) return sum[rt];
ll mid=(l+r)>>1,ans=0;
pushdown(rt,r-l+1);
if(L<=mid) ans=(ans+query(L,R,l,mid,rt<<1))%p;
if(R>mid) ans=(ans+query(L,R,mid+1,r,rt<<1|1))%p;
return ans;
}
void dfs1(ll x,ll f,ll deep){
dep[x]=deep;
fa[x]=f;
siz[x]=1;
ll maxson=-1;
for(ll i=head[x];i;i=from[i]){
ll y=to[i];
if(y==f) continue;
dfs1(y,x,deep+1);
siz[x]+=siz[y];
if(siz[y]>maxson){
son[x]=y;
maxson=siz[y];
}
}
}
void dfs2(ll x,ll f){
id[x]=++tim;
top[x]=f;
mp[tim]=a[x];
if(son[x]) dfs2(son[x],f);
for(ll i=head[x];i;i=from[i]){
ll y=to[i];
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
int main()
{
memset(lazy,-1,sizeof(lazy));
scanf("%lld",&n);r=1;p=1e15;
for(ll i=1;i<n;i++){
ll x,y;
scanf("%lld",&x);
add(x+1,i+1);add(i+1,x+1);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,n,1);
scanf("%lld",&m);
for(ll i=1;i<=m;i++){
char op[20];ll x,y,z;
scanf("%s",op);
if(op[0]=='i'){
scanf("%lld",&x);y=1;z=1;
ll Ans=0;x++;ll nx=x;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
Ans=(Ans+query(id[top[x]],id[x],1,n,1))%p;
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
Ans=(Ans+query(id[x],id[y],1,n,1))%p;
x=nx;y=1;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
update(id[top[x]],id[x],z,1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(id[x],id[y],z,1,n,1);
ll ans=dep[nx];
printf("%lld
",ans-Ans);
}
else {
scanf("%lld",&x);z=0;x++;
printf("%lld
",query(id[x],id[x]+siz[x]-1,1,n,1)%p);
update(id[x],id[x]+siz[x]-1,z,1,n,1);
}
}
return 0;
}
[SHOI2012]魔法树
其实就是软件包管理器的加强版
(Code Below:)
#include <bits/stdc++.h>
#define ll long long
#define res register int
#define mid (l+r>>1)
using namespace std;
const int maxn=100000+10;
int n,q,head[maxn],to[maxn<<1],nxt[maxn<<1],tot;
ll sum[maxn<<2],lazy[maxn<<2];
int top[maxn],son[maxn],dep[maxn],fa[maxn],id[maxn],siz[maxn],tim;
inline int read(){
res x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>=10) print(x/10);
putchar(x%10+'0');
}
inline void swap(int &a,int &b){res t=a;a=b;b=t;}
inline void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
inline void pushdown(int rt,int len){
if(lazy[rt]){
sum[rt<<1]+=lazy[rt]*(len-(len>>1));
sum[rt<<1|1]+=lazy[rt]*(len>>1);
lazy[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
lazy[rt]=0;
}
}
void update(int L,int R,int C,int l,int r,int rt){
if(L <= l && r <= R){
sum[rt]+=(r-l+1)*C;
lazy[rt]+=C;
return ;
}
pushdown(rt,r-l+1);
if(L <= mid) update(L,R,C,l,mid,rt<<1);
if(R > mid) update(L,R,C,mid+1,r,rt<<1|1);
pushup(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
if(L <= l && r <= R){
return sum[rt];
}
ll ans=0;
pushdown(rt,r-l+1);
if(L <= mid) ans+=query(L,R,l,mid,rt<<1);
if(R > mid) ans+=query(L,R,mid+1,r,rt<<1|1);
return ans;
}
inline void add(int x,int y){
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs1(int x,int f){
dep[x]=dep[f]+1;
siz[x]=1;
fa[x]=f;
ll maxson=-1;
for(res i=head[x];i;i=nxt[i]){
res y=to[i];
if(y==f) continue;
dfs1(y,x);
siz[x]+=siz[y];
if(maxson<siz[y]){
son[x]=y;
maxson=siz[y];
}
}
}
void dfs2(int x,int topf){
id[x]=++tim;
top[x]=topf;
if(son[x]) dfs2(son[x],topf);
for(res i=head[x];i;i=nxt[i]){
res y=to[i];
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
int main()
{
n=read();
res x,y;
for(res i=1;i<n;i++){
x=read(),y=read();
add(x+1,y+1);add(y+1,x+1);
}
dfs1(1,1);
dfs2(1,1);
q=read();
char ch;res u,v,d;
while(q--){
ch=getchar();
while(ch!='A'&&ch!='Q') ch=getchar();
if(ch=='A'){
u=read()+1,v=read()+1,d=read();
for(;top[u]!=top[v];){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
update(id[top[u]],id[u],d,1,n,1);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
update(id[u],id[v],d,1,n,1);
}
else {
u=read()+1;
printf("%lld
",query(id[u],id[u]+siz[u]-1,1,n,1));
}
}
return 0;
}