結果

問題 No.2337 Equidistant
ユーザー kotatsugamekotatsugame
提出日時 2023-06-02 21:45:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,080 ms / 4,000 ms
コード長 1,987 bytes
コンパイル時間 1,279 ms
コンパイル使用メモリ 89,036 KB
実行使用メモリ 38,380 KB
最終ジャッジ日時 2024-12-28 17:08:59
合計ジャッジ時間 19,792 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cassert>
#include<atcoder/modint>
#include<atcoder/lazysegtree>
using namespace std;
#include<vector>
struct LCA{
	int N;
	vector<vector<int> >G,parent;
	vector<int>depth,ch;
	LCA(int N_=0):N(N_),G(N_),depth(N_),ch(N_)
	{
		int lg=0;
		while((1<<lg)+1<N_)lg++;
		parent.assign(lg+1,vector<int>(N_));
	}
	void add_edge(int u,int v)
	{
		G[u].push_back(v);
		G[v].push_back(u);
	}
	void dfs(int u,int p,int d)
	{
		depth[u]=d;
		parent[0][u]=p;
		ch[u]=1;
		for(int v:G[u])if(v!=p)
		{
			dfs(v,u,d+1);
			ch[u]+=ch[v];
		}
	}
	void build(int root=0)
	{
		dfs(root,-1,0);
		for(int k=1;k<parent.size();k++)
		{
			for(int i=0;i<N;i++)
			{
				if(parent[k-1][i]==-1)parent[k][i]=-1;
				else parent[k][i]=parent[k-1][parent[k-1][i]];
			}
		}
	}
	int lca(int u,int v)
	{
		if(depth[u]>depth[v])swap(u,v);
		for(int k=0;k<parent.size();k++)if(depth[v]-depth[u]>>k&1)v=parent[k][v];
		if(u==v)return u;
		for(int k=parent.size();k--;)if(parent[k][u]!=parent[k][v])
		{
			u=parent[k][u];
			v=parent[k][v];
		}
		return parent[0][u];
	}
	int dist(int u,int v)
	{
		int w=lca(u,v);
		return depth[u]+depth[v]-2*depth[w];
	}
	int up(int u,int k)
	{
		assert(depth[u]>=k);
		for(int i=0;i<parent.size();i++)if(k>>i&1)u=parent[i][u];
		return u;
	}
};
int N,Q;
int main()
{
	cin>>N>>Q;
	LCA lca(N);
	for(int i=1;i<N;i++)
	{
		int a,b;cin>>a>>b;
		a--,b--;
		lca.add_edge(a,b);
	}
	lca.build(0);
	for(;Q--;)
	{
		int s,t;cin>>s>>t;
		s--,t--;
		int w=lca.lca(s,t);
		int ds=lca.depth[s]-lca.depth[w];
		int dt=lca.depth[t]-lca.depth[w];
		if((ds+dt)%2!=0)
		{
			cout<<"0\n";
			continue;
		}
		if(ds==dt)
		{
			assert(ds>=1);
			int cnt=N;
			cnt-=lca.ch[lca.up(s,ds-1)];
			cnt-=lca.ch[lca.up(t,dt-1)];
			cout<<cnt<<"\n";
			continue;
		}
		if(ds<dt)swap(s,t),swap(ds,dt);
		int d=(ds+dt)/2;
		assert(ds>d);
		assert(d>=1);
		int x=lca.up(s,d-1);
		int y=lca.parent[0][x];
		cout<<lca.ch[y]-lca.ch[x]<<"\n";
	}
}
0