Submission #230423

---

Source Code Expand

//木の頂点a,b間の距離がXならば、a,b間をつないだときにできる閉路の長さはX+1になりそう。(だって、aからbまでいって、戻ってくるんだから)
//そうすると、2点間の距離にO(1)とかO(logN)とかで応える必要があるな…… (LCA!!)
//a,b間の距離 = aから根までの距離 + bから根までの距離 - a,bのLCAから根までの距離*2
//しかし、LCA高速処理ってどうやるんだ…(大まかな設計は↑でよい。細かい設計をしよう)
//なお、1番(node[0])を「根」とする。

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> PI;

int N;
int x,y;
int Q;
int a,b;

struct NODE{
	vector<int> to;
	int oya;
	int size;
	int dist;
}node[100000];

void BFS( int st )
{
	static queue<PI> que;
	PI now;
	int i;
	que.push( PI(st,0) );
	node[st].oya = st;
	
	while( !que.empty() ){
		now = que.front();
		que.pop();
		if( node[now.first].dist != -1 )
			continue;
		node[now.first].dist = now.second;

		for( i = 0; i < node[now.first].size; i++ ){
			if( node[ node[now.first].to[i] ].oya == -1 ){
				node[ node[now.first].to[i] ].oya = now.first;
				que.push( PI( node[now.first].to[i], now.second+1 ) );
			}
		}
	}
}

//頂点a,bのLCAを求める
int LCA( int a, int b )
{
	if( a == b )
		return a;
	if( node[a].dist > node[b].dist )
		return LCA( node[a].oya, b );
	if( node[b].dist > node[a].dist )
		return LCA( a, node[b].oya );
	if( node[a].dist == node[b].dist )
		return LCA( node[a].oya, node[b].oya );
}

int main()
{
	int i,ans;
	cin >> N;
	
	if( N > 3000 )
		return 0;
		
	for( i = 0; i < N; i++ ){
		node[i].size = 0;
		node[i].dist = -1;
		node[i].oya = -1;
	}
	
	for( i = 0; i < N-1; i++ ){
		cin >> x >> y;x--;y--;
		node[x].to.push_back(y);
		node[y].to.push_back(x);
		node[x].size++;
		node[y].size++;
	}
	
	//node[0]を根としたときの、全頂点-根間の距離を記録
	BFS(0);
	
	cin >> Q;
	for( i = 0; i < Q; i++ ){
		cin >> a >> b;a--;b--;
		ans = node[a].dist + node[b].dist - node[LCA(a,b)].dist*2 + 1;	//なぜか+1しないとWA生える
		cout << ans << endl;
	}
	return 0;
}

Submission Info

Judge Result