結果

問題 No.2337 Equidistant
ユーザー kotatsugamekotatsugame
提出日時 2023-06-02 21:45:38
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,155 ms / 4,000 ms
コード長 1,987 bytes
コンパイル時間 1,058 ms
コンパイル使用メモリ 88,056 KB
実行使用メモリ 38,040 KB
最終ジャッジ日時 2023-08-28 03:06:14
合計ジャッジ時間 18,394 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 7 ms
4,376 KB
testcase_07 AC 7 ms
4,380 KB
testcase_08 AC 7 ms
4,376 KB
testcase_09 AC 7 ms
4,376 KB
testcase_10 AC 6 ms
4,376 KB
testcase_11 AC 783 ms
30,700 KB
testcase_12 AC 791 ms
30,648 KB
testcase_13 AC 783 ms
30,728 KB
testcase_14 AC 784 ms
30,632 KB
testcase_15 AC 786 ms
30,624 KB
testcase_16 AC 805 ms
30,768 KB
testcase_17 AC 782 ms
30,560 KB
testcase_18 AC 780 ms
30,744 KB
testcase_19 AC 791 ms
30,640 KB
testcase_20 AC 772 ms
30,560 KB
testcase_21 AC 896 ms
38,040 KB
testcase_22 AC 705 ms
31,152 KB
testcase_23 AC 726 ms
31,516 KB
testcase_24 AC 1,103 ms
35,788 KB
testcase_25 AC 757 ms
31,492 KB
testcase_26 AC 1,155 ms
35,400 KB
testcase_27 AC 765 ms
31,584 KB
testcase_28 AC 759 ms
31,384 KB
権限があれば一括ダウンロードができます

ソースコード

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