【文件属性】：
文件名称：树链剖分模板题
文件大小：3KB
文件格式：CPP
更新时间：2018-06-08 03:25:19
树链剖分
#include
#include
#include
#define N 30003
#define INF 2147483647
using namespace std;
int n,f[N][20],dep[N],siz[N],son[N],top[N],tot,pos[N],w[N];
int Max[N*4],Sum[N*4];
vector to[N];
void dfs1(int x){
siz[x]=1;
int sz=to[x].size();
for(int i=0;isiz[son[x]])son[x]=y;
}
}
void dfs2(int x,int root){
top[x]=root;
pos[x]=++tot;
if(son[x])dfs2(son[x],root);
int sz=to[x].size();
for(int i=0;i>1;
if(P<=mid)update(k*2,l,mid,P,V);
else update(k*2+1,mid+1,r,P,V);
Max[k]=max(Max[k*2],Max[k*2+1]);
Sum[k]=Sum[k*2]+Sum[k*2+1];
}
void up(int &x,int goal){
for(int i=15;i>=0;--i)
if(dep[f[x][i]]>=goal)x=f[x][i];
}
int lca(int x,int y){
if(dep[x]>dep[y])up(x,dep[y]);
if(dep[x]=0;--i)
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
int getm(int k,int l,int r,int L,int R){
if(L<=l && r<=R)return Max[k];
int res=-INF,mid=(l+r)>>1;
if(L<=mid)res=max(res,getm(k*2,l,mid,L,R));
if(R>mid)res=max(res,getm(k*2+1,mid+1,r,L,R));
return res;
}
int gets(int k,int l,int r,int L,int R){
if(L<=l && r<=R)return Sum[k];
int res=0,mid=(l+r)>>1;
if(L<=mid)res+=gets(k*2,l,mid,L,R);
if(R>mid)res+=gets(k*2+1,mid+1,r,L,R);
return res;
}
int main(){
scanf("%d",&n);
for(int i=1,a,b;i
