yukicoder : No.2337 Equidistant

これはすんなり。
https://yukicoder.me/problems/no/2337

問題

木を成す無向グラフが与えられる。
以下のクエリに答えよ。

• 2点s,tが与えられる。s,tからの最短距離が一致する頂点dは何個あるか。

解法

s,tの真ん中の点をmとする。Nから、mよりs寄りの頂点の数とt寄りの頂点の数を引けばよい。
これはLCA算出ができるようにしておき、頂点のDFS訪問順のラベル付けを行っておけば容易に行える。

int N,Q;
vector<int> E[200005];
int P[21][200005],D[200005];
int L[202020],R[202020],id;

void dfs(int cur) {
	L[cur]=id++;
	sort(ALL(E[cur]));
	FORR(e,E[cur]) if(e!=P[0][cur]) D[e]=D[cur]+1, P[0][e]=cur, dfs(e);
	R[cur]=id;
}
int getpar(int cur,int up) {
	int i;
	FOR(i,20) if(up&(1<<i)) cur=P[i][cur];
	return cur;
}

int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}

	//0以外を根にするならP[0][root]=rootが必要
	dfs(0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	
	while(Q--) {
		cin>>x>>y;
		x--,y--;
		if(D[x]%2!=D[y]%2) {
			cout<<0<<endl;
			continue;
		}
		if(D[x]<D[y]) swap(x,y);
		int lc=lca(x,y);
		if(D[x]==D[y]) {
			x=getpar(x,D[x]-D[lc]-1);
			y=getpar(y,D[y]-D[lc]-1);
			cout<<N-(R[x]-L[x])-(R[y]-L[y])<<endl;
		}
		else {
			y=getpar(x,D[x]-(D[lc]+(D[x]-D[y])/2));
			x=getpar(x,D[x]-D[y]-1);
			cout<<(R[y]-L[y])-(R[x]-L[x])<<endl;
		}
		
		
	}
	
		
}

まとめ

典型っぽい気もするけど他で出てないのかな。