最近有根号分治的题都没那么熟悉，想到了方向感也很差，故写一点题解。
LCA查询
看到题目中的条件 \(\sum k \le 10^5\)
说明 \(k \le S\) 的个数很多，\(S \le k\) 的个数很少。
那么对于前者，考虑一开始最朴素的 \(O(S^2)\) 的暴力，枚举集合中的两个点，求 \(LCA\) 总时间复杂度 \(O( \frac{N}{S} \cdot S^2 \cdot log N)\)。
对于后者，若 \(n^2\) 肯定不行。考虑到我们的限制：一共也就 \(n\) 个点，先让 \(A\) 集合里的点向上跳，将点都标起来，若跳到该点已经走过就不用再跑，这样保证了每个点只会被遍历 \(1\) 次。再让 \(B\) 里的点向上跳，若碰到 \(A\) 的标记，进行深度统计，不再向上（应为上面不可能更优）。时间复杂度 \(O(\frac{N}{S} \cdot N)\)
跑起来挺快。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n,m,dep[N];
int siza,a[N];
int sizb,b[N];
int st[N][18];
vector<int> e[N];
void dfs(int u,int fa){
dep[u] = dep[fa] + 1;
st[u][0] = fa;
for(int i = 1;i<=17;++i)st[u][i] = st[st[u][i-1]][i-1];
for(int v : e[u])if(v ^ fa)dfs(v,u);
}
int LCA(int x,int y){
if(dep[x] > dep[y])swap(x,y);
int t = dep[y] - dep[x];
for(int i = 17;~i;--i)if(t&(1<<i))y = st[y][i];
if(x == y)return x;
for(int i = 17;~i;--i)if(st[x][i] ^ st[y][i])
x = st[x][i], y = st[y][i];
return st[x][0];
}
int vis[N];
int main(){
scanf("%d%d",&n,&m);
for(int i = 1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
e[u].push_back(v),e[v].push_back(u);
}
dfs(1,0);
while(m--){
scanf("%d",&siza); for(int i = 1;i<=siza;++i)scanf("%d",&a[i]);
scanf("%d",&sizb); for(int i = 1;i<=sizb;++i)scanf("%d",&b[i]);
int ans = 0;
if(siza <= 100 && sizb <= 100){
for(int i = 1;i<=siza;++i)
for(int j = 1;j<=sizb;++j)
ans = max(ans,dep[LCA(a[i],b[j])]);
printf("%d\n",ans);
}else{
for(int i = 1;i<=siza;++i){
int now = a[i];
while(now){
if(vis[now] > 0)break;
vis[now] = 1;
now = st[now][0];
}
}
for(int i = 1;i<=sizb;++i){
int now = b[i];
while(now){
if(vis[now] > 0){
if(vis[now] == 1)ans = max(ans,dep[now]);
break;
}
vis[now] = 2;
now = st[now][0];
}
}
memset(vis,0,sizeof (int)*(n+5));
printf("%d\n",ans);
}
}
return 0;
}