LCA 最近公共祖先（模板）

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <cstring>
 4 #include <vector>
 5 #define N 100005
 6 using namespace std;
 7 vector <int> vec[N] ;
 8 vector <pair<int,int> > query[N];
 9 struct node{
10     int first , second;
11 }e;
12 
13 vector <node> query[N];
14 
15 int vis[N] , pre[N] , ans[N];
16 int Find(int x){
17     if(pre[x] == x){
18         return x;
19     }else{
20         pre[x] = Find(pre[x]);
21         return pre[x];
22     }
23 }
24 void dfs(int u , int fa){
25     
26     pre[u] = u;
27     vis[u] = 1;
28     for(int i = 0 ; i < vec[u].size() ; i ++){
29         int v = vec[u][i];
30         if(v == fa) continue;
31         dfs(v , u);
32     }
33     
34     for(int i = 0 ; i < query[u].size() ; i++){
35         int v = query[u][i].first;
36         int id = query[u][i].second;
37         if(vis[v] == 1){
38             ans[id] = Find(v);
39         }
40     }
41 
42     pre[u] = fa;
43 }
44 
45 int main(){
46     int T;
47     scanf("%d" ,&T);
48     while(T --){
49         int n , x, y;
50         scanf("%d" , &n);
51         for(int i = 0 ; i < n - 1 ; i ++){
52             scanf("%d%d" , &x , &y);
53             vec[x].push_back(y);
54             vec[y].push_back(x);
55             vis[y] = 1;
56         }
57         for(int i = 1 ; i <= n ; i ++ ){
58             cout << i << "==========" << endl;
59             for(int k = 0 ; k  <  vec[i].size() ; k ++){
60                 cout << vec[i][k] << " ";
61             }
62             cout << endl;
63         }
64         int q;
65         scanf("%d",&q);
66         for(int i = 0 ; i < q ; i ++){
67             scanf("%d%d" , &x , &y);
68             query[x].push_back({y , i});
69             query[y].push_back({x , i});
70         }
71         for(int i = 1 ; i <= n ; i ++){
72             if(vis[i] == 0){
73                 memset(vis , 0 ,sizeof(vis));
74                 dfs(i , -1);
75                 break;
76             }
77         }
78         for(int i = 0 ; i < q ; i ++){
79             printf("%d
" ,ans[i]);
80         }
81     }
82 }
LCA 最近公共祖先 （模板）

LCA 最近公共祖先（模板）
