[BZO3572][HNOI2014]世界树：虚树+倍增

分析

思维难度几乎为\(0\)的虚树码农（并不）题。
代码

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)

#define irin(i,a,b) for(register int i=(a);i>=(b);--i)

#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)

#define itrav(i,a) for(register int i=ihead[a];i;i=ie[i].nxt)

typedef long long LL;

using std::cin;

using std::cout;

using std::endl;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

const int MAXN=3e5+5;

int n,q,ecnt,head[MAXN];

int tot,id[MAXN],num[MAXN],len,st[MAXN<<1][21],pos[MAXN];

int dep[MAXN],siz[MAXN],anc[MAXN][21];

int m,mm,h[MAXN<<1],hh[MAXN],top,sta[MAXN];

int iecnt,ihead[MAXN];

int ans[MAXN];

bool isc[MAXN];

struct Edge{

	int to,nxt;

}e[MAXN<<1];

inline void add_edge(int bg,int ed){

	++ecnt;

	e[ecnt].to=ed;

	e[ecnt].nxt=head[bg];

	head[bg]=ecnt;

}

void dfs1(int x,int pre,int depth){

	id[x]=++tot;

	num[tot]=x;

	st[++len][0]=id[x];

	pos[x]=len;

	dep[x]=depth;

	siz[x]=1;

	anc[x][0]=pre;

	trav(i,x){

		int ver=e[i].to;

		if(ver==pre) continue;

		dfs1(ver,x,depth+1);

		st[++len][0]=id[x];

		siz[x]+=siz[ver];

	}

}

void buildst(){

	int lim=log2(len);

	rin(i,1,lim) rin(j,1,len-(1<<i)+1)

		st[j][i]=std::min(st[j][i-1],st[j+(1<<(i-1))][i-1]);

}

void buildanc(){

	rin(i,1,20) rin(j,1,n)

		anc[j][i]=anc[anc[j][i-1]][i-1];

}

inline int lca(int x,int y){

	x=pos[x],y=pos[y];

	if(x>y) std::swap(x,y);

	int lim=log2(y-x+1);

	return num[std::min(st[x][lim],st[y-(1<<lim)+1][lim])];

}

inline bool cmp(int x,int y){

	return id[x]<id[y];

}

struct iedge{

	int to,nxt;

}ie[MAXN];

inline void add_iedge(int bg,int ed){

	++iecnt;

	ie[iecnt].to=ed;

	ie[iecnt].nxt=ihead[bg];

	ihead[bg]=iecnt;

}

void build_itree(){

	std::sort(h+1,h+m+1,cmp);

	rin(i,2,mm) h[++m]=lca(h[i-1],h[i]);

	h[++m]=1;

	std::sort(h+1,h+m+1,cmp);

	m=std::unique(h+1,h+m+1)-h-1;

	top=0;

	rin(i,1,m){

		while(top&&id[h[i]]>id[sta[top]]+siz[sta[top]]-1) add_iedge(sta[top-1],sta[top]),--top;

		sta[++top]=h[i];

	}

	while(top>1) add_iedge(sta[top-1],sta[top]),--top;

	--top;

}

struct ctrl{

	int pos,dis;

	inline friend bool operator < (ctrl A,ctrl B){

		return A.dis==B.dis?A.pos<B.pos:A.dis<B.dis;

	}

}c[MAXN];

void dfs2(int x){

	if(isc[x]) c[x]=(ctrl){x,0};

	else c[x]=(ctrl){0,(int)1e9};

	itrav(i,x){

		int ver=ie[i].to;

		dfs2(ver);

		c[x]=std::min(c[x],(ctrl){c[ver].pos,c[ver].dis+dep[ver]-dep[x]});

	}

}

void dfs3(int x,int pre){

	if(pre) c[x]=std::min(c[x],(ctrl){c[pre].pos,c[pre].dis+dep[x]-dep[pre]});

	itrav(i,x){

		int ver=ie[i].to;

		dfs3(ver,x);

	}

}

inline int getveranc(int x,int pre){

	int ret=x;

	irin(i,20,0)

		if(dep[anc[ret][i]]>dep[pre])

			ret=anc[ret][i];

	return ret;

}

inline int climb(int x,int y){

	int ret=x,tt=0;

	while(y){

		if(y&1) ret=anc[ret][tt];

		++tt;

		y>>=1;

	}

	return ret;

}

void dfs4(int x,int pre){

	ans[c[x].pos]+=siz[x];

	itrav(i,x){

		int ver=ie[i].to,veranc=getveranc(ver,x);

		dfs4(ver,x);

		ans[c[x].pos]-=siz[veranc];

		if(c[x].pos==c[ver].pos)

			ans[c[x].pos]+=siz[veranc]-siz[ver];

		else{

			int mid=0;

			if((dep[ver]-dep[x]+c[ver].dis-c[x].dis)&1) mid=dep[ver]-(((dep[x]+dep[ver]+c[ver].dis-c[x].dis)>>1)+1);

			else if(c[x].pos<c[ver].pos) mid=dep[ver]-(((dep[x]+dep[ver]+c[ver].dis-c[x].dis)>>1)+1);

			else mid=dep[ver]-((dep[x]+dep[ver]+c[ver].dis-c[x].dis)>>1);

			mid=climb(ver,mid);

			ans[c[x].pos]+=siz[veranc]-siz[mid];

			ans[c[ver].pos]+=siz[mid]-siz[ver];

		}

	}

}

/*

const int MAXN=3e5+5;

int n,q,ecnt,head[MAXN];

int tot,id[MAXN],num[MAXN],len,st[MAXN<<1][21],pos[MAXN];

int dep[MAXN],siz[MAXN],anc[MAXN][21];

int m,mm,h[MAXN<<1],hh[MAXN],top,sta[MAXN];

int iecnt,ihead[MAXN];

int ans[MAXN];

bool isc[MAXN];

*/

void clear_itree(){

	iecnt=0;

	rin(i,1,m) ihead[h[i]]=ans[h[i]]=0,isc[h[i]]=false;

}

int main(){

	n=read();

	rin(i,2,n){

		int u=read(),v=read();

		add_edge(u,v);

		add_edge(v,u);

	}

	dfs1(1,0,1);

	buildst();

	buildanc();

	q=read();

	while(q--){

		m=mm=read();

		rin(i,1,m) h[i]=hh[i]=read(),isc[h[i]]=true;

		build_itree();

		dfs2(1);

		dfs3(1,0);

		dfs4(1,0);

		rin(i,1,mm) printf("%d ",ans[hh[i]]);

		putchar('\n');

		clear_itree();

	}

	return 0;

}
巴特西

[BZO3572][HNOI2014]世界树：虚树+倍增

分析

代码

最新文章

热门文章
