bzoj3784 树上的路径

传送门

#include 
const int N=500005;
int to[N<<1],edge,Next[N<<1],last[N],siz[N],g,L[N*20],R[N*20],w[N<<1];
int v[N*20],vis[N],cnt,st[N*20][21],lstl,lstr,bit[N*20],n,m,x,y,z;
void add(int x,int y,int z){
	to[++edge]=y;
	Next[edge]=last[x];
	last[x]=edge;
	w[edge]=z;
}
void find(int x,int y,int &g,int nn){
	siz[x]=1;
	int mx=0;
	for (int i=last[x];i;i=Next[i]){
		int u=to[i];
		if (u==y || vis[u]) continue;
		find(u,x,g,nn);
		siz[x]+=siz[u];
		mx=std::max(mx,siz[u]);
	}
	if (mx<=nn/2 && nn-siz[x]<=nn/2) g=x;
} 
void dfs(int x,int y,int dis){
	v[++cnt]=dis,L[cnt]=lstl,R[cnt]=lstr;
	for (int i=last[x];i;i=Next[i]){
		int u=to[i];
		if (u==y || vis[u]) continue;
		dfs(u,x,dis+w[i]);
	}
}
void div(int x){
	vis[x]=1;
	v[++cnt]=0,lstl=cnt;
	for (int i=last[x];i;i=Next[i]){
		int u=to[i];
		if (vis[u]) continue;
		lstr=cnt;
		dfs(u,x,w[i]);
		siz[u]=cnt-lstr;
	}
	for (int i=last[x];i;i=Next[i]){
		int u=to[i];
		if (vis[u]) continue;
		find(u,0,g,siz[u]);
		div(g);
	}
}
void init(){
	for (int i=2;i<=cnt;i++) bit[i]=bit[i>>1]+1;
	for (int i=1;i<=cnt;i++) st[i][0]=i;
	for (int i=1;i<=20;i++)
		for (int j=1;j+(1<v[st[j+(1<v[st[r-(1< q;
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;it.l) q.push(note{t.x,t.l,t.mx-1,RMQ(t.l,t.mx-1)});
		if (t.r>t.mx) q.push(note{t.x,t.mx+1,t.r,RMQ(t.mx+1,t.r)});
	}
}