Submission #5896934

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
int N;

class LCA{
private:
	vector<vector<int>> v;
	vector<vector<int>> parent;
	vector<int> depth;
//	int parent[21][100010];
//	int depth[100010] = {};
	void dfs(int n,int m,int d){
		parent[0][n] = m;
		depth[n] = d;
		for(auto x:v[n]){
			if(x!=m) dfs(x,n,d+1);
		}
	}
public:
	LCA(int N,int root,vector<vector<int>>& tree){
		v = tree;
		parent = vector<vector<int>>(21,vector<int>(N+1,0));
		depth = vector<int>(N+1,0);
		dfs(root,-1,0);
		for(int j=0;j+1<20;j++){
			for(int i=1;i<=N;i++){
				if(parent[j][i]<0) parent[j+1][i] = -1;
				else parent[j+1][i] = parent[j][parent[j][i]];
			}
		}
	}
	void init(int N,int root){
		dfs(root,-1,0);
		for(int j=0;j+1<20;j++){
			for(int i=1;i<=N;i++){
				if(parent[j][i]<0) parent[j+1][i] = -1;
				else parent[j+1][i] = parent[j][parent[j][i]];
			}
		}
	}
	int lca(int n,int m){
		if(depth[n]>depth[m]) swap(n,m);
		for(int j=0;j<20;j++){
			if((depth[m]-depth[n]) >> j&1) m = parent[j][m];
		}
		if(n==m) return n;
		for(int j=19;j>=0;j--){
			if(parent[j][n]!=parent[j][m]){
				n = parent[j][n];
				m = parent[j][m];
			}
		}
		return parent[0][n];
	}
	int dep(int n){return depth[n];}
};
int Q,x,y,a,b;

int main(){
	cin >> N;
	vector<vector<int>> tree(N+1);
	for(int i=0;i<N-1;i++){
		cin >> x >> y;
		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	LCA lca(N,1,tree);
	cin >> Q;
	for(int i=0;i<Q;i++){
		cin >> a >> b;
		int p = lca.lca(a,b);
		cout << lca.dep(a)+lca.dep(b)+1-2*lca.dep(p) << endl;	
	}
}

Submission Info

Judge Result