树链剖分模版

const  int maxn=10000+5;
const  int maxm=maxn+maxn;
int v[maxm];
int prev[maxm];
int info[maxm];
int q[maxn];
int idx[maxn];
int dep[maxn];
int size[maxn];
int belong[maxn];
int father[maxn];
bool vis[maxn] ;
int head[maxn];
int len[maxn];
int l,r,ans,cnt=0;
int n,nedge=0;

inline void insert(int x,int y){
	++negde;
	v[nedge]=y;prev[nedge]=info[x];info[x]=nedge;
} 

void split(){
	memset(dep,-1,sizeof(dep));
	l=0;
	dep[q[r=1]=1]=0;
	father[1]=-1;
	while(l<r){
		int x=q[++l];
		for(int y=info[x];y;y=prev[y]){
			if(dep[v[y]]==-1){
				dep[q[++r]=v[y]]=dep[x]+1;
				father[v[y]]=x;
			}
		}
	}
	for(int i=n;i;i--){
		int x=q[i],p=-1;
		size[x]=1;
		for(int y=info[x];y;y=prev[y])
		  if(vis[v[y]]) {
		  	size[x]+=size[v[y]];
		  	if(p==-1||size[v[y]]>size[p])
		  	   p=v[y];
		  }
		  if(p==-1){
		  	idx[x]=len[++cnt]=1;
		  	belong[head[cnt]=x]=cnt;
		  }
		  else{
		  	idx[x]=++len[belong[x]=belong[p]];
		  	head[belong[x]]=x;
		  }
		  vis[x]=true;
	}
}