歸納（四）：樹鏈剖分
剖分的意義
能用線段樹搞想要的信息。
（其實可以只用來求LCA）
需要的東西
七個數組，在兩次dfs中處理出來。
dfs1:
dep[]:深度
fa[]:父親
son[]:重兒子
siz[]:子樹大小（包括自己）
dfs2:
indexx:新的編號
id[]:新的編號
top[]:鏈頂
int son[maxn],fa[maxn],dep[maxn],siz[maxn];
int id[maxn],indexx,top[maxn];
void dfs1(int nd,int p,int deep) {
dep[nd]=deep;
fa[nd]=p;
siz[nd]=1;
int maxson=-1;
for(int i=h[nd];~i;i=e[i].nxt) {
if(e[i].v==p) continue;
dfs1(e[i].v,nd,deep+1);
siz[nd]+=siz[e[i].v];
if(siz[e[i].v]>maxson)
son[nd]=e[i].v,maxson=siz[e[i].v];
}
}
void dfs2(int nd,int chain) {
id[nd]=++indexx;
top[nd]=chain;
if(!son[nd]) return ;
dfs2(son[nd],chain);
for(int i=h[nd];~i;i=e[i].nxt) {
if(e[i].v==fa[nd] || e[i].v==son[nd]) continue;
dfs2(e[i].v,e[i].v);
}
}
其實很好理解。
但不加線段樹的樹鏈剖分是沒有靈魂的。
樹鏈剖分求LCA
最最最基礎的操作了。
原理是不在同一條重鏈上，就直接跳鏈。
int lca(int lnd,int rnd) {
while(top[lnd]!=top[rnd]) {
if(dep[top[lnd]]<dep[top[rnd]]) std::swap(lnd,rnd);
lnd=fa[top[lnd]];
}
return dep[lnd]<dep[rnd]?lnd:rnd;
}
【模板】樹鏈剖分
如題，已知一棵包含N個結點的樹（連通且無環），每個節點上包含一個數值，需要支持以下操作：
操作1： 格式： 1 x y z 表示將樹從x到y結點最短路徑上所有節點的值都加上z
操作2： 格式： 2 x y 表示求樹從x到y結點最短路徑上所有節點的值之和
操作3： 格式： 3 x z 表示將以x為根節點的子樹內所有節點值都加上z
操作4： 格式： 4 x 表示求以x為根節點的子樹內所有節點值之和
用到了線段樹。
重鏈由于重新編號，可以保證編號連續。
同時因為dfs序的原因，一個節點和它的子樹的編號也是連續的。
分別可以解決1、2和3、4操作。
子樹的操作十分簡單，直接modify或者query，左端點是id[nd]，右端點是id[nd]+siz[nd]-1。
路徑與求LCA同理。
void Pmodify(int lnd,int rnd,int c) {
while(top[lnd]!=top[rnd]) {
if(dep[top[lnd]]<dep[top[rnd]]) std::swap(lnd,rnd);
modify(1,1,n,id[top[lnd]],id[lnd],c);
lnd=fa[top[lnd]];
}
if(dep[lnd]>dep[rnd]) std::swap(lnd,rnd);
modify(1,1,n,id[lnd],id[rnd],c);
}
int Pquery(int lnd,int rnd) {
int ans=0;
while(top[lnd]!=top[rnd]) {
if(dep[top[lnd]]<dep[top[rnd]]) std::swap(lnd,rnd);
vall=0;
query(1,1,n,id[top[lnd]],id[lnd]);
ans=(ans+vall)%mod;
lnd=fa[top[lnd]];
}
if(dep[lnd]>dep[rnd]) std::swap(lnd,rnd);
vall=0;
query(1,1,n,id[lnd],id[rnd]);
return (ans+vall)%mod;
}
void Smodify(int nd,int c) {
modify(1,1,n,id[nd],id[nd]+siz[nd]-1,c);
}
int Squery(int nd) {
vall=0;
query(1,1,n,id[nd],id[nd]+siz[nd]-1);
return vall;
}
不要在意query是void型的事情，已經摒棄這種寫法了。
例題（一）
[NOI2015]軟件包管理器
安裝是把根到節點的路徑改為1，卸載是子樹改為0。
注意lazy_tag是有可能是0的，要把laz初值賦成-1。
其實這個是基本常識。
比如：
Challenge 5
我二月份就已經錯過了。
其他題基本都是大同小異。
例題（二）
加油吧！
我才不會呢！
代碼
#include<bits/stdc++.h>
const int maxn=3e4+5;
const int oo=0x3f3f3f3f;
inline int read() {
int x,f=1;char ch;while(!isdigit(ch=getchar())) (ch=='-') && (f=-1);
for(x=ch^'0';isdigit(ch=getchar());x=(x<<3)+(x<<1)+(ch^'0'));
return f*x;
}
int n;
struct Edge {
int nxt,v;
}e[maxn<<1];
int h[maxn],tot,w[maxn],wt[maxn];
void add_edge(int u,int v) {
e[++tot].v=v;
e[tot].nxt=h[u];
h[u]=tot;
}
int vmax[maxn<<2],sum[maxn<<2],vall;
inline void pushup(int rt) {
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
vmax[rt]=std::max(vmax[rt<<1],vmax[rt<<1|1]);
}
void build(int rt,int l,int r) {
if(l==r) {
sum[rt]=vmax[rt]=wt[l];
return ;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
void modify(int rt,int l,int r,int pos,int c) {
if(l==r) {
sum[rt]=vmax[rt]=c;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid) modify(rt<<1,l,mid,pos,c);
else modify(rt<<1|1,mid+1,r,pos,c);
pushup(rt);
}
int Squery(int rt,int l,int r,int L,int R) {
int mid=(l+r)>>1,ans=0;
if(L<=l && r<=R) return sum[rt];
if(L<=mid) ans+=Squery(rt<<1,l,mid,L,R);
if(R>mid) ans+=Squery(rt<<1|1,mid+1,r,L,R);
pushup(rt);
return ans;
}
int Mquery(int rt,int l,int r,int L,int R) {
int mid=(l+r)>>1,ans=-oo;
if(L<=l && r<=R) return vmax[rt];
if(L<=mid) ans=std::max(ans,Mquery(rt<<1,l,mid,L,R));
if(R>mid) ans=std::max(ans,Mquery(rt<<1|1,mid+1,r,L,R));
pushup(rt);
return ans;
}
int son[maxn],fa[maxn],siz[maxn],dep[maxn];
int indexx,top[maxn],id[maxn];
void dfs1(int nd,int p,int deep) {
dep[nd]=deep;
fa[nd]=p;
siz[nd]=1;
int maxson=-1;
for(int i=h[nd];~i;i=e[i].nxt) {
if(e[i].v==p) continue;
dfs1(e[i].v,nd,deep+1);
siz[nd]+=siz[e[i].v];
if(siz[e[i].v]>maxson) {
son[nd]=e[i].v;
maxson=siz[e[i].v];
}
}
}
void dfs2(int nd,int chain) {
id[nd]=++indexx;
wt[indexx]=w[nd];
top[nd]=chain;
if(!son[nd]) return ;
dfs2(son[nd],chain);
for(int i=h[nd];~i;i=e[i].nxt) {
if(e[i].v==fa[nd] || e[i].v==son[nd]) continue;
dfs2(e[i].v,e[i].v);
}
}
int qmax(int lnd,int rnd) {
int ans=-oo;
while(top[lnd]!=top[rnd]) {
if(dep[top[lnd]]<dep[top[rnd]]) std::swap(lnd,rnd);
ans=std::max(ans,Mquery(1,1,n,id[top[lnd]],id[lnd]));
lnd=fa[top[lnd]];
}
if(dep[lnd]>dep[rnd]) std::swap(lnd,rnd);
return std::max(ans,Mquery(1,1,n,id[lnd],id[rnd]));
}
int qsum(int lnd,int rnd) {
int ans=0;
while(top[lnd]!=top[rnd]) {
if(dep[top[lnd]]<dep[top[rnd]]) std::swap(lnd,rnd);
ans+=Squery(1,1,n,id[top[lnd]],id[lnd]);
lnd=fa[top[lnd]];
}
if(dep[lnd]>dep[rnd]) std::swap(lnd,rnd);
ans+=Squery(1,1,n,id[lnd],id[rnd]);
return ans;
}
int main() {
memset(h,-1,sizeof(h));
n=read();
for(int i=1;i<n;i++) {
int a=read(),b=read();
add_edge(a,b);
add_edge(b,a);
}
for(int i=1;i<=n;i++) w[i]=read();
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n);
int q=read();
while(q--) {
char s[10];
scanf("%s",s);
int x=read(),y=read();
switch(s[1]) {
case 'H':modify(1,1,n,id[x],y);break;
case 'M':printf("%d\n",qmax(x,y));break;
case 'S':printf("%d\n",qsum(x,y));break;
default:break;
}
}
return 0;
}
浙公網安備 33010602011771號