struct BIT{
int sz;
vector<int> c;
void build(int s){
c.resize(s+1);
sz=s;
}
int lowbit(int x){
return x&(-x);
}
void add(int x,int y){
x++;
for(;x<=sz;x+=lowbit(x)) c[x]+=y;
}
int sum(int x){
x++;
int ans=0;x=min(x,sz);
for(;x;x-=lowbit(x)) ans+=c[x];
return ans;
}
};
struct DFS{
int sz[N],mxs[N],ct[N],fu[N];
BIT c1[N],c2[N];
int gt_rt(int x,int fa,int st){
int q=x;
mxs[x]=max(mxs[x],sz[st]-sz[x]);
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(ct[y]||y==fa) continue;
int p=gt_rt(y,x,st);
if(mxs[p]<mxs[q]) q=p;
}
return q;
}
void dfs(int x,int fa){
sz[x]=1,mxs[x]=0;
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(y==fa||ct[y]) continue;
dfs(y,x);
sz[x]+=sz[y],mxs[x]=max(mxs[x],sz[y]);
}
}
void build(int x){
ct[x]=1,sz[x]++;
c1[x].build(sz[x]),c2[x].build(sz[x]);
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
if(ct[y]) continue;
dfs(y,x);
int rt=gt_rt(y,x,y);
fu[rt]=x,sz[rt]=sz[y];build(rt);
}
}
void pre(){
mxs[0]=1e9;
memset(ct,0,sizeof(ct));
memset(fu,0,sizeof(fu));
dfs(1,0);
int rt=gt_rt(1,0,1);
build(rt);
}
void jia(int x,int y){
for(int i=x;i;i=fu[i]) c1[i].add(Tl.dis(x,i),y);
for(int i=x;fu[i];i=fu[i]) c2[i].add(Tl.dis(x,fu[i]),y);
}
int he(int x,int y){
int ans=c1[x].sum(y);
for(int i=x;fu[i];i=fu[i]){
int z=y-Tl.dis(x,fu[i]);
if(z<0) continue;
ans+=c1[fu[i]].sum(z)-c2[i].sum(z);
}
return ans;
}
}T;
标签:sz,return,struct,int,void,点分树
From: https://www.cnblogs.com/hubingshan/p/17916206.html