tarjan+并查集做法 $Wa \ on \ \# 13$ 求调。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;

const int NR = 5e5 + 10;

struct edge
{
	int nxt, to;
}e[NR * 2];

int head[NR], cnt;

void add(int x, int y)
{
	e[++cnt].nxt = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}

struct Query_sets
{
	int to, id;
};

vector<Query_sets> q[NR];
int f[NR];
int vis[NR];

int find(int x)
{
	if (x != f[x]) f[x] = find(f[x]);
	return f[x];
}

int ans[NR];

void tarjan(int x, int fa)
{
	f[x] = x;
	for (int i = head[x]; i; i = e[i].nxt)
	{
		int y = e[i].to;
		if (y == fa) continue;
		tarjan(y, x);
	}
	for (int i = 0; i < (int)q[x].size(); i ++)
	{
		int y = q[x][i].to;
		if (vis[y])
		{
			ans[q[x][i].id] = find(y);
		}
	}
	vis[x] = 1;
	f[x] = fa;
}

int main()
{
	int n, m, s;
	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);
		add(y, x);
	}
	for (int i = 1; i <= m; i ++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		q[a].push_back((Query_sets){b, i});
		q[b].push_back((Query_sets){a, i});
	}
	tarjan(s, s);
	for (int i = 1; i <= m; i ++)
	{
		printf("%d\n", ans[i]);
	}
	return 0;
}