tarjan求LCA

模版题 https://www.luogu.org/problemnew/show/P3379
讲解 https://www.bilibili.com/video/av41067872/?p=4&t=1591
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 5e5+5;
 4 struct qnode{
 5     int x,y,lca;
 6 }query[maxn];
 7 int fa[maxn];
 8 bool vis[maxn];
 9 vector<int> G[maxn];
10 vector<int> Q[maxn];
11 void init(){
12     for(int i=0; i<maxn; i++)fa[i]=i;
13 }
14 int find(int x){
15     return fa[x]==x?x:fa[x]=find(fa[x]);
16 }
17 void tarjan(int u){
18     vis[u] = true;
19     for(auto qid:Q[u]){
20         if(query[qid].x == u){
21             if(vis[query[qid].y]){
22                 query[qid].lca = find(query[qid].y);
23             }
24         }
25         else{
26             if(vis[query[qid].x]){
27                 query[qid].lca = find(query[qid].x);
28             }
29         }
30     }
31     for(auto v:G[u]){
32         if(vis[v]) continue;
33         tarjan(v);
34         fa[v] = u;
35     }
36 }
37 int main(){
38     init();
39     int n, m, s;
40     scanf("%d%d%d", &n, &m, &s);
41     int x, y;
42     for(int i=1; i<n; i++){
43         scanf("%d%d", &x, &y);
44         G[x].push_back(y);
45         G[y].push_back(x);
46     }
47     for(int i=1; i<=m;i++){
48         scanf("%d%d", &query[i].x, &query[i].y);
49         Q[query[i].x].push_back(i);
50         Q[query[i].y].push_back(i);
51     }
52     tarjan(s);
53     for(int i=1;i<=m; i++){
54         printf("%d
",query[i].lca);
55     }
56 }