**Nhận xét**: Trong một tập đỉnh thì 2 đỉnh có thứ tự duyệt DFS xa nhau nhất sẽ có LCA gần gốc nhất, vì vậy, chỉ cần chọn đỉnh có thứ tự duyệt nhỏ nhất và đỉnh có thứ tự duyệt lớn nhất trong tập. Điều này có thể xử lí bằng đường đi Euler: duy trì một mảng $st[u]$, biểu thị thứ tự duyệt DFS của đỉnh $u$.
**Code mẫu**:
```cpp
//author: kaoruko
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int M = 1e9 + 7;
int n, q, t;
int st[N], en[N];
vector<int> adj[N];
int Min(int x, int y){
if(st[x] < st[y])return x;
return y;
}
int Max(int x, int y){
if(st[x] > st[y])return x;
return y;
}
void dfs(int u, int pa){
st[u] = ++t;
for(auto it : adj[u]){
if(it != pa)dfs(it, u);
}
en[u] = t;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
dfs(1, -1);
st[n+1] = ++t; en[n+1] = t;
while(q--){
int k; cin >> k;
int mn = n+1, mx = 0;
while(k--){
int u; cin >> u;
mn = Min(mn, u); mx = Max(mx, u);
}
cout << mn << ' ' << mx << '\n';
}
}
nihahaha
Created at
6 likes