大佬教程收集整理的这篇文章主要介绍了树链剖分，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
如果我们需要建立一棵树，而且需要维护树上路径的信息，较为方便的做法就是树链剖分。
树剖主要有两种形式：
一般来说，树链剖分指的是重链剖分。本篇博客主要讲的也是重链剖分。
几乎所有树上问题都可以用树链剖分解决，这里给出一些作用：
(son[x]) :重子节点 表示 (X) 子节点重子树最大的节点。 (dfn[x]) : (dfs)序。 (rk[x]) ：表示该节点(dfs) 序对应的节点。 (sizes[x])： 子节点个数。 (f[x]) : 父亲节点。 (d[x]) ：节点深度。
基础的就这六个，此外可能还有定义的边权值，就根据题意即可。
树链剖分最基础的部分就是两次(dfs) 。
首先看代码：
void dfs1(int x,int last){
d[x]=d[last]+1;//深度
sizes[x]=1;//节点本身也是其子树
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(y==last) conTinue;
fa[y]=x;//父亲
dfs1(y,X);
sizes[x]+=sizes[y];
if(sizes[y]>sizes[son[x]]||!son[x]) son[x]=y;
//对于节点x，其子树最大的儿子就是其重儿子
//如果儿子节点子树大小相同,那么重儿子随便哪个都可以
}
}
void dfs2(int x,int topfather){
dfn[x]=++cnt;//dfs序
top[x]=topfather;//这个点所在重链的顶端,对于求lca和链有极大帮助
rk[cnt]=x;//dfs序所对应的节点编号
if(!son[x]) return;
dfs2(son[x],topfather);//我们首先进入重儿子来保证一条重链上各个节点dfs序连续
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(y!=son[x]&&y!=fa[x]) dfs2(y,y);//位于轻链底端，top为本身
}
}
对于每一部分都有解释，就不再多说了。
我们已经知道了该树的重链，以及(dfs) 序，那么在 (O(log n)) 的时间里我们就可以求出(x,y) 节点的 (lca) 。(没有学过倍增 (lca) 建议先学倍增)
我们的思路是要把 (x,y) 两个节点弄到同一条重链上，因此我们需要将深度深的节点不断蹦到其对应重链顶端的父亲上。
当在同一条重链上时，比较两点深度，深度浅的就是其公共父亲。
int lca(int x,int y){
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(d[x]>d[y]) swap(x,y);
return x;
}
因为树剖在树上，所以用线段树存储比较方便。
对应的操作也大多是跟线段树相同的操作：
struct tree{
int l,r,sum,lazy;
}t[n];
int len(int X){
return t[x].r-t[x].l+1;
}
void pushdown(int X){//懒标记
if(t[x].lazy){
int lz=t[x].lazy,ls=x<<1,rs=x<<1|1;
t[ls].lazy=(t[ls].lazy+lz)%mod;
t[rs].lazy=(t[rs].lazy+lz)%mod;
t[ls].sum=(t[ls].sum+lz*len(ls))%mod;
t[rs].sum=(t[rs].sum+lz*len(rs))%mod;
t[x].lazy=0;
}
}
void pushup(int X){
t[x].sum=(t[x<<1].sum+t[x<<1|1].sum)%mod;
}
void update(int l,int r,int c,int X){//区间修改
if(t[x].l>=l&&t[x].r<=r){
t[x].lazy=(t[x].lazy+C)%mod;
t[x].sum=(t[x].sum+len(X)*C)%mod;
return;
}
pushdown(X);
int mid=t[x].l+t[x].r>>1;
if(mid>=l) update(l,r,c,x<<1);
if(mid<r) update(l,r,c,x<<1|1);
pushup(X);
}
void build(int l,int r,int X){
t[x].l=l;t[x].r=r;t[x].sum=0;
if(l==r){
t[x].sum=val[rk[l]];//给这个节点赋值
return;
}
int mid=l+r>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
pushup(X);
}
模板题，包含更改路径权值，求路径权值，更改点权值，求子树点值和。
void updatetree(int x,int y,int C){//对于树上一个节点到另一个节点增加值
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);//根据深度进行枚举
update(dfn[top[x]],dfn[x],c,1);
x=fa[top[x]];
}
if(dfn[x]>dfn[y]) swap(x,y);
update(dfn[x],dfn[y],c,1);
}
int sum(int x,int y){//两点之间的值
int res=0;
while(top[x]!=top[y]){//两者链的顶端不同
if(d[top[x]]<d[top[y]]) swap(x,y);//先跳深度大的
res=(res+query(dfn[top[x]],dfn[x],1))%mod;
x=fa[top[x]];
}
if(dfn[x]>dfn[y]) swap(x,y);
return (res+query(dfn[x],dfn[y],1))%mod;//两者在同一条链上，直接求就行
}
else if(x==3){
scanf("%lld%lld",&l,&z);
update(dfn[l],dfn[l]+sizes[l]-1,z,1);//子树区间的右端点
//在之前求过以l为根的子树大小，因此直接加上就是子树。
}
int query(int l,int r,int X){//线段树上加和
if(t[x].l>=l&&t[x].r<=r) return t[x].sum;
pushdown(X);
int mid=t[x].l+t[x].r>>1,res=0;
if(mid>=l) res+=query(l,r,x<<1);
if(mid<r) res+=query(l,r,x<<1|1);
return res%mod;
}
scanf("%lld",&l);
printf("%lldn",query(dfn[l],dfn[l]+sizes[l]-1,0));
又是一道模板题，操作涉及：更改点权值，求路径最大权值，求路径权值
int query_sum(int l,int r,int X){
int ans=0;
if(l<=t[x].l&&r>=t[x].r) return t[x].sum;
int mid=t[x].l+t[x].r>>1;
if(l<=mid) ans+=query_sum(l,r,x<<1);
if(r>mid) ans+=query_sum(l,r,x<<1|1);
return ans;
}
int query_max(int l,int r,int X){
int ans=0;
if(l<=t[x].l&&r>=t[x].r) return t[x].maxn;
int mid=t[x].l+t[x].r>>1;
if(l<=mid) ans=max(ans,query_max(l,r,x<<1));
if(r>mid) ans=max(ans,query_max(l,r,x<<1|1));
return ans;
}
int tree_sum(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
ans+=query_sum(dfn[top[x]],dfn[x],1);
x=f[top[x]];
}
if(dfn[x]>dfn[y]) swap(x,y);
ans=max(ans,query_sum(dfn[x],dfn[y],1));
return ans;
}
int tree_max(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
ans=max(ans,query_max(dfn[top[x]],dfn[x],1));
x=f[top[x]];
}
if(dfn[x]>dfn[y]) swap(x,y);
ans=max(ans,query_max(dfn[x],dfn[y],1));
return ans;
}
这道题其实也是一道模板题。
我们需要记录线段树里的左儿子的颜色和右儿子的颜色，如果两个区间中间颜色相同，那么答案需要减少。
#include<bits/stdc++.h>
using namespace std;
#definE int long long
const int n=4e5+5;
int nxt[n],head[n],ver[n],tot;
int Lc,Rc;//记录序列左边和右边的颜色
struct node{
int l,r,sum,lc,rc;
int lazy;
}t[n];
int n,m;
int dfn[n],rk[n],d[n],f[n],sizes[n],cnt,son[n],top[n];
int col[n];
void add(int x,int y){
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void build(int l,int r,int X){
t[x].l=l,t[x].r=r,t[x].sum=0;
if(l==r) return;
int mid=l+r>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
}
void pushdown(int X){
if(t[x].lazy){
int L=x<<1,R=x<<1|1;
t[L].lazy=t[R].lazy=t[x].lazy;
t[L].sum=t[R].sum=1;
t[L].lc=t[L].rc=t[x].lc;
t[R].lc=t[R].rc=t[x].lc;
t[x].lazy=0;
}
}
void pushup(int X){
t[x].lc=t[x<<1].lc;
t[x].rc=t[x<<1|1].rc;
int res=t[x<<1].sum+t[x<<1|1].sum;
// cout<<res<<endl;
if(t[x<<1].rc==t[x<<1|1].lC) res--;//中间颜色相同
t[x].sum=res;
}
.....dfs过程
void update(int l,int r,int x,int color){
if(t[x].l==l&&t[x].r==r){
t[x].sum=t[x].lazy=1;
t[x].lc=t[x].rc=color;
return;
}
pushdown(X);
int mid=t[x].l+t[x].r>>1;
if(r<=mid) update(l,r,x<<1,color);
else if(l>mid) update(l,r,x<<1|1,color);
else{
update(l,mid,x<<1,color);
update(mid+1,r,x<<1|1,color);
}
pushup(X);
}
int query(int l,int r,int L,int R,int X){
if(t[x].l==L) Lc=t[x].lc;//获取边界值
if(t[x].r==R) Rc=t[x].rc;
if(t[x].l==l&&t[x].r==r) return t[x].sum;
pushdown(X);
int mid=t[x].l+t[x].r>>1;
if(r<=mid) return query(l,r,L,R,x<<1);
else if(l>mid) return query(l,r,L,R,x<<1|1);
else{
int ans=query(l,mid,L,R,x<<1)+query(mid+1,r,L,R,x<<1|1);
if(t[x<<1].rc==t[x<<1|1].lC) ans--;
return ans;
}
pushup(X);
}
void solve1(int x,int y,int C){
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
update(dfn[top[x]],dfn[x],1,c);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
update(dfn[x],dfn[y],1,c);
}
int solve2(int x,int y){
int ans=0,ans1=-1,ans2=-1;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]){
swap(x,y);swap(ans1,ans2);
}
ans+=query(dfn[top[x]],dfn[x],dfn[top[x]],dfn[x],1);
if(Rc==ans1) ans--;
ans1=Lc;
x=f[top[x]];
}
if(d[x]<d[y]) swap(x,y),swap(ans1,ans2);
ans+=query(dfn[y],dfn[x],dfn[y],dfn[x],1);//忘写了:(
if(Rc==ans1) ans--;
if(Lc==ans2) ans--;
return ans;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%lld",&col[i]);
for(int i=1,x,y;i<n;i++){
scanf("%lld%lld",&x,&y);add(x,y);add(y,X);
}
cnt=0;dfs1(1,0);dfs2(1,1);
cnt=1;build(1,n,1);
for(int i=1;i<=n;i++){
update(dfn[i],dfn[i],1,col[i]);
}
while(m--){
char op[3];int a,b,c;
scanf("%s",op);//字符串读入问题
// cout<<op<<endl;
if(op[0]=='C'){
scanf("%lld%lld%lld",&a,&b,&c);
solve1(a,b,c);
}
else{
scanf("%lld%lld",&a,&b);
printf("%lldn",solve2(a,b));
}
}
system("pause");
return 0;
}
算是半个模板题： 对于操作一，我们可以统计(X)到根节点未安装的软件包的个数，然后区间修改为已安装。
对于操作二，我们可以统计(X)所在子树已安装软件包的个数，然后将子树修改为未安装。
int sum(int X){
int fx=top[x],ans=0;
while(fX){
ans+=dfn[x]-dfn[fx]-query(dfn[fx],dfn[x],rt)+1;
update(dfn[fx],dfn[x],1,rt);
x=fa[fx];
fx=top[x];
}
ans+=dfn[x]-dfn[0]-query(dfn[0],dfn[x],rt)+1;
update(dfn[0],dfn[x],1,rt);
return ans;
}
{ if(op=="install") printf("%lldn",sum(X));
else if(op=="uninstall"){
printf("%lldn",query(dfn[x],dfn[x]+sizes[x]-1,rt));
update(dfn[x],dfn[x]+sizes[x]-1,0,rt);
}
}
这题还是比较有难度的。
我们看见最长路径最短时间这类题目，都可以想到二分答案来解决。
如果成立，那么就比 (mid) 答案小，如果不行，那么比 (mid) 大。
我们先把树建好，然后依次求两点之间的路径，根据 (lca) 求。
那么二分答案的范围是：([R-maxL,R+1]) ,其中 (R) 是两点之间长度最大值，(maxL) 是边权值最大。
在二分答案中，我们首先判断所有路径是否大于(mid)，如果大于，说明我们不能把这条路径删除。
利用 树上差分 记录当前路径走了多少次，再记录一下当前路走过的个数。
增加一些判断就可以解决题目。一些细节在代码里。
bool check(int X){
int res=0;memset(C,0,sizeof(C));
for(int i=1;i<=m;i++)//只判断大路径
if(t[i].dis>X){//大于路径，因此我们不能把其删除
C[t[i].l]++;C[t[i].r]++;//树上差分，记录
C[t[i].lca]-=2;
res++;
}
for(int i=n;i>=1;i--){
C[f[rk[i]]]+=C[rk[i]];//每次差分值累加到父亲节点，记录经过次数
if(val[rk[i]]>=R-x//这条边权值减去合适
&&C[rk[i]]==res)//被所有大路径经过————表示这些路径的距离比二分值大
return 1;
}
return 0;
}
以上是大佬教程为你收集整理的树链剖分全部内容，希望文章能够帮你解决树链剖分所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。