LCA
Alliances
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define endl "\n" 4 typedef long long ll; 5 const int N = 5e5 + 5; 6 vector<int>edge[N], occupy[N]; 7 int n, now, father[N][25], dist[N], vis[N], lca[N], DFN[N], DFN_POS[N]; 8 void DFS(int s) { 9 vis[s] = 1; 10 DFN[s] = ++now; DFN_POS[now] = s; 11 for (auto i : edge[s]) { 12 if (vis[i])continue; 13 father[i][0] = s; 14 dist[i] = dist[s] + 1; 15 DFS(i); 16 } 17 } 18 int LCA(int x, int y) { 19 if (dist[x] < dist[y])swap(x, y); 20 int z = dist[x] - dist[y]; 21 for (int i = 0; i <= 20 && z; i++, z >>= 1) { 22 if (z & 1)x = father[x][i]; 23 } 24 if (x == y)return x; 25 for (int i = 20; i >= 0; i--) { 26 if (father[x][i] != father[y][i])x = father[x][i], y = father[y][i]; 27 } 28 return father[x][0]; 29 } 30 int dis(int x, int y) { 31 return dist[x] + dist[y] - 2 * dist[LCA(x, y)]; 32 } 33 int main() { 34 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 35 cin >> n; 36 for (int i = 0; i < n - 1; i++) { 37 int x, y; 38 cin >> x >> y; 39 edge[x].push_back(y); 40 edge[y].push_back(x); 41 } 42 father[1][0] = 1; 43 DFS(1); 44 for (int i = 1; i <= 20; i++) { 45 for (int j = 1; j <= n; j++) { 46 if (father[j][i - 1])father[j][i] = father[father[j][i - 1]][i - 1]; 47 } 48 } 49 int k; cin >> k; 50 for (int i = 1; i <= k; i++) { 51 int sz, x; 52 cin >> sz; 53 for (int j = 1; j <= sz; j++) { 54 cin >> x; 55 if (j == 1)lca[i] = x; 56 else lca[i] = LCA(lca[i], x); 57 occupy[i].push_back(DFN[x]); 58 } 59 sort(occupy[i].begin(), occupy[i].end()); 60 } 61 int T = 1; cin >> T; 62 while (T--) { 63 int cap, sz, all_lca; cin >> cap >> sz; 64 vector<int>Bang(sz); 65 for (int i = 0; i < sz; i++) { 66 cin >> Bang[i]; 67 if (!i)all_lca = lca[Bang[i]]; 68 else all_lca = LCA(all_lca, lca[Bang[i]]); 69 } 70 //注意:不在以所有帮派共同lca为顶点的子树中判断条件是 71 //LCA(all_lca,cap)!=all_lca 72 if (LCA(all_lca, cap) != all_lca) { 73 cout << dis(all_lca, cap) << endl; 74 continue; 75 } 76 int ans = INT_MAX; 77 for (int i = 0; i < sz; i++) { 78 auto x = lower_bound(occupy[Bang[i]].begin(), occupy[Bang[i]].end(), DFN[cap]); 79 if (x != occupy[Bang[i]].begin())ans = min(ans, dis(cap, LCA(cap, DFN_POS[*prev(x)]))); 80 if (x != occupy[Bang[i]].end())ans = min(ans, dis(cap, LCA(cap, DFN_POS[*x]))); 81 } 82 cout << ans << endl; 83 } 84 return 0; 85 }