Submission #1756085

---

Source Code Expand

#include <bits/stdc++.h>
#define INF 1e+9
using namespace std;

typedef pair<int,int> P;

class RMQ{
	int n,seg,init;
	vector<P> dat;
public:
	RMQ(int siz,int def) : n(siz),init(def),seg(1){
		while(seg < n) seg *= 2;
		dat.resize(seg * 2 - 1);
		for(int i = 0;i < seg;i++) dat[i + seg - 1] = P(init,i);
		for(int i = seg - 2;i >= 0;i--) dat[i] = min(dat[i * 2 + 1],dat[i * 2 + 2]);
	}
	void update(int i,int x){
		i += seg - 1;
		dat[i] = P(x,i - seg + 1);
		while(i){
			i = (i - 1) / 2;
			dat[i] = min(dat[i * 2 + 1],dat[i * 2 + 2]); //do
		}
	}
	P get(int a = 0,int b = -1,int k = 0,int l = 0,int r = -1){
		if(b == -1) b = seg;
		if(r == -1) r = seg;
		if(b <= l || r <= a) return P(init,-1);
		if(a <= l && r <= b) return dat[k];
		return min(get(a,b,k * 2 + 1,l,(l + r) / 2),get(a,b,k * 2 + 2,(l + r) / 2,r)); //do
	}
};

class EulerTour{
	int cnt;
	public:
	vector<int> first,last,depth,line;
	vector<vector<int> > g;
	EulerTour(int n) : g(n),first(n),last(n),depth(n){}
	void add(int u, int v) {
		g[u].push_back(v);
		g[v].push_back(u);
	}
	void build(){
		cnt = 0;
		dfs(0,-1,0);
	}
	void dfs(int v,int par,int d){
		depth[v] = d;
		line.push_back(v);
		first[v] = cnt++;
		for(int next : g[v]){
			if(next == par) continue;
			dfs(next,v,d + 1);
			cnt++;
			line.push_back(v);
		}
	}
};


int main(){
	int n,q;
	cin >> n;
	EulerTour et(n);
	for(int i = 0;i < n - 1;i++){
		int x,y;
		cin >> x >> y; x--;y--;
		et.add(x,y);
	}
	et.build();
	RMQ rmq(et.line.size(),INF);
	for(int i = 0;i < et.line.size();i++) rmq.update(i,et.depth[et.line[i]]);
	cin >> q;
	for(int i = 0;i < q;i++){
		int x,y;
		cin >> x >> y; x--;y--;
		int p = rmq.get(min(et.first[x],et.first[y]),max(et.first[x],et.first[y]) + 1).first;
		cout << et.depth[x] + et.depth[y] - p * 2 + 1 << endl;
	}
	return 0;
}

Submission Info

Judge Result