#include <cstdio> #include <iostream> #include <vector>
using namespace std;
const int SIZE = 5e6 + 1;
struct edge { int to_node, id; edge(int t, int i): to_node(t), id(i) {} ~edge() = default; };
vector<int> edges[SIZE]; vector<edge> querys[SIZE]; int father[SIZE], mark[SIZE], ans[SIZE];
int n, m, s;
int getfa(int x) { if (father[x] == x) return x; else return father[x] = getfa(father[x]); }
void tarjan(int x) { mark[x] = 1; for (auto i = edges[x].begin(); i != edges[x].end(); i++) { if (mark[*i]) continue; tarjan(*i); father[*i] = x; } for (auto i = querys[x].begin(); i != querys[x].end(); i++) { int y = (*i).to_node, id = (*i).id; if (mark[y] == 2) ans[id] = getfa(y); } mark[x] = 2; }
int main() { int u, v; scanf("%d%d%d", &n, &m, &s); for (int i = 1; i <= n; i++) { father[i] = i; mark[i] = 0; } for (int i = 1; i < n; i++) { scanf("%d%d", &u, &v); edges[u].emplace_back(v); edges[v].emplace_back(u); } int x, y; for (int i = 1; i <= m; i++) { scanf("%d%d", &x, &y); if (x == y) ans[i] = 0; else { querys[x].emplace_back(edge(y, i)); querys[y].emplace_back(edge(x, i)); } } tarjan(s); for (int i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0; }
|