rt，欧拉序+st表

#include <stdio.h>
#include <string.h>
#include <iostream> 
using namespace std;
const int N = 500050;
struct node {
	int u, v, next;
} e[N*2];
int h[N], tot = 1;
void add(int x, int y) {
	e[tot] = {x, y, h[x]};
	h[x] = tot++;
	e[tot] = {y, x, h[y]};
	h[y] = tot++;
}
int f[22][N];

int n, m, s;
int ol[N*2], cnt = 0, pos[N*2], dpos[N*2];

void dfs(int x, int fa) {
	
	ol[++cnt] = x;
	
	for(int i=h[x]; i; i=e[i].next) {
		int v = e[i].v;
		if(v == fa) continue;
		
		dfs(v, x);
		ol[++cnt] = x;
	}
}

int main() {
	
	freopen("P3379_1.in", "r", stdin);
	
	scanf("%d%d%d", &n, &m, &s);
	for(int i=1; i<n; ++i) {
		int x, y; scanf("%d%d", &x, &y);
		add(x, y);
	}
	
	dfs(s, 0);
	
	//ol[1..cnt] 欧拉序列(原值) 
	//造st表
	
	memset(f, 0x3f, sizeof f);
	for(int i=1; i<=cnt; ++i) {
		if(pos[ol[i]] == 0) {
			pos[ol[i]] = i;
			dpos[pos[ol[i]]] = ol[i];
		}
		f[0][i] = pos[ol[i]];
	}
	
	for(int j=1; j<=20; ++j) {
		for(int i=1; i<=cnt; ++i) {
			f[j][i] = min(f[j-1][i], f[j-1][i+(1<<(j-1))]);
		}
	} 
	
	for(int i=1; i<=m; ++i) {
		int a, b; scanf("%d%d", &a, &b);
		int x=20;
		while(b-a+1 < (1<<x)) --x;
		printf("%d\n", dpos[min(f[x][a], f[x][b-(1<<x)+1])]);
	}
	
	return 0;
}