周日和黄主力吃饭的时候他问我，你会用树链剖分写LCA吗？我说，树链剖分上的LCA和普通倍增LCA有什么区别吗？然后被黄主力大骂一通。。

今天看到一道树链剖分裸题BZOJ3631，就尝试一下直接在树链剖分的同时LCA的方法

树链剖分LCA基本思路：如果两个点不在一条重链上，就移动high[belong[x]]更小的点到fa[belong[x]]

时间复杂度：O(n log n)  空间复杂度：O(n)

模板

int getlca(int x,int y){
	for(;belong[x]!=belong[y];x=father[belong[x]])if(high[belong[x]]<high[belong[y]])swap(x,y);
	if(pos[x]>pos[y])return y;else return x;
}

BZOJ3631（树链剖分套树状数组）

#include<cstdio>
#include<iostream>
#define N 333333
using namespace std;
int n,i,x,y,tot,sz,ans,a[N],c[N],first[N],size[N],father[N],high[N],pos[N],belong[N],last[N<<1],next[N<<1];
bool vis[N];
void insert(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
void dfs(int x){
	size[x]=1;vis[x]=1;
	for(int i=first[x];i;i=next[i])
		if(!vis[y=last[i]]){
			father[y]=x;high[y]=high[x]+1;
			dfs(y);size[x]+=size[y];
		}
}
void dfs2(int x,int f){
	int now=0;pos[x]=++sz;belong[x]=f;
	for(int i=first[x];i;i=next[i])if(size[y=last[i]]>size[now]&&high[x]<high[y])now=y;
	if(!now)return;dfs2(now,f);
	for(int i=first[x];i;i=next[i])if(high[x]<high[y=last[i]]&&now!=y)dfs2(y,y);
}
int lowbit(int x){return x&(-x);}
void change(int x,int z){for(;x<=n&&x;x+=lowbit(x))c[x]+=z;}
int query(int x){ans=0;for(;x;x-=lowbit(x))ans+=c[x];return ans;}
void queryin(int x,int y){//树链剖分LCA部分
	for(;belong[x]!=belong[y];x=father[belong[x]]){
		if(high[belong[x]]<high[belong[y]])swap(x,y);
		change(pos[belong[x]],1);change(pos[x]+1,-1);
	}
	if(pos[x]>pos[y])swap(x,y);
	change(pos[x],1);change(pos[y]+1,-1);
}
int main(){
	scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),insert(x,y),insert(y,x);
	dfs(1);dfs2(1,1);
	for(i=1;i<n;i++)queryin(a[i],a[i+1]);
	for(i=2;i<=n;i++)change(pos[a[i]],-1),change(pos[a[i]]+1,1);
	for(i=1;i<=n;i++)printf("%d\n",query(pos[i]));
}

这样写的树链剖分真是短，压代码以后1031B，BZOJ上最短

BZOJ1103 树剖傻逼题，直接树剖LCA再合适不过了

#include<cstdio>
#define N 252500
int n,i,x,y,tot,m,sum,ans,id,fir[N],la[N<<1],ne[N<<1],c[N],fa[N],bl[N],pos[N],h[N],sz[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void add(int x,int y){for(;x<=n;x+=x&-x)c[x]+=y;}char s[9];
int qu(int x){for(sum=0;x;x-=x&-x)sum+=c[x];return sum;}
void dfs(int x){
	int i,y;sz[x]=1;
	for(i=fir[x];i;i=ne[i])if(fa[x]!=(y=la[i]))fa[y]=x,h[y]=h[x]+1,dfs(y),sz[x]+=sz[y];
}
void dfs2(int x,int f){
    int now=0,i;pos[x]=++id;bl[x]=f;
    for(i=fir[x];i;i=ne[i])if(sz[y=la[i]]>sz[now]&&h[x]<h[y])now=y;
    if(!now)return;dfs2(now,f);
    for(i=fir[x];i;i=ne[i])if(h[x]<h[y=la[i]]&&now!=y)dfs2(y,y);
}
int main(){
	for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	dfs(1);dfs2(1,1);for(i=2;i<=n;i++)add(i,1);
	for(scanf("%d",&m),m+=n-1;m--;){
		scanf("%s",s);if(s[0]=='W'){
			scanf("%d",&x);
			for(ans=0;bl[1]!=bl[x];x=fa[bl[x]])ans+=qu(pos[x])-qu(pos[bl[x]]-1);
			printf("%d\n",ans+qu(pos[x])-qu(pos[1]-1));
		}else scanf("%d%d",&x,&y),add(pos[y],-1);
	}
}

• 相关文章推荐
• 全局相关文章