1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXON = 1000010;
int dep[MAXON];//dep[i]代表编号为i的点所处的深度
int lg[MAXON];
class Graph
{
private:
struct edge
{
int to;//这条边到达的点
int next;//下一条边
}Edge[MAXON];
int head[MAXON];//head[i]表示由i开始的第一条边的编号
int tot;//总边数
int grand[500010][30];
int fa[MAXON];
public:
Graph()
{
tot = 0;
}
void add_dege(int from, int to)
{
tot++;//当前边的编号
Edge[tot].to = to;
if (from != -1)
Edge[tot].next = head[from];//插入在前
head[from] = tot;//由于这条边插入在了前面,故当前边就是由from开始的第一条边
}
void dfs(int from, int now)
{
fa[now] = from;//记录父节点
int start = head[now];//从第一个子节点开始找
if (from != -1)//若不是根节点,深度为父节点深度+1(根节点为0)
dep[now] = dep[from] + 1;
//int g = log2(dep[now]) ;
int g = lg[dep[now]];
if (from != -1)//根节点没有父节点
grand[now][0] = from;//2^0=1,即父节点
for (int i = 1; i <= g; i++)
{
grand[now][i] = grand[grand[now][i - 1]][i - 1];//状态转移方程
}
while (start)//一个一个找孩子
{
if (Edge[start].to == from)//若相连节点不是父节点
{
start = Edge[start].next;
continue;
}
dfs(now, Edge[start].to);//继续搜索子节点
start = Edge[start].next;//搜索下一个子节点
}
}
int lca(int a, int b)
{
if (dep[a] > dep[b])//统一b深度大于a
{
a = a + b;//a此时等于原来的a,b之和
b = a - b;//b此时等于原来的a
a = a - b;//a此时等于原来的b
}//神奇的交换方法
int deep = dep[b] - dep[a];//深度差
//int step = log2(deep);
int step = lg[deep];//最大要走的步数
for (int i = step; i >= 0; i--)//先让b跳到和a同一深度
{
if (dep[grand[b][i]] < dep[a]) continue;//跳过头了,不跳
else
{
b = grand[b][i];//没跳过头,跳
}
}
if (a == b) return a;//若相等,则已经找到LCA
step = lg[dep[a]]; //要走的步数
//step = log2(dep[a]);
for (int i = step; i >= 0; i--)
{
if (grand[a][i] == grand[b][i]) continue;//跳过头了,不跳
else//没跳过头,跳
{
a = grand[a][i];
b = grand[b][i];
}
}
return fa[a];//最后他们的父节点就是LCA
}
};
Graph G;
int main()
{
int n, m, s;
//cin >> n >> m >> s;
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= n; i++) //常熟优化,预先算出log_2(i)+1的值，用的时候直接调用就可以了
lg[i] = lg[i - 1] + (1 << lg[i - 1] == i); //看不懂的可以手推一下
n--;
while (n--)
{
int a, b;
//cin >> a >> b;
scanf("%d%d", &a, &b);
G.add_dege(a, b);
G.add_dege(b, a);
}
G.dfs(-1, s);
while (m--)
{
int a, b;
//cin >> a >> b;
scanf("%d%d", &a, &b);
int ans = G.lca(a, b);
if (ans == -1)
printf("%d\n", s);
//cout << s << endl;
else
printf("%d\n", ans);
//cout << ans << endl;
}
return 0;
}
|
