题意

给一棵树，$m$次询问，每次询问给两个点集问从两个点集中各取一个点的$LCA$的最大深度。

思路

二分答案。对于某个二分过程中得到的$Mid$，如果可行则两个点集在$Mid$所在的深度存在公共的祖先。枚举点集内的点，倍增找到他在这个深度的祖先就行。

代码

#include 
     
      #define DBG(x) cerr << #x << " = " << x << endlusing namespace std;const int N = 100000 + 5;const int M = 200000 + 5;int n, m, k1, k2;int tot, head[N];int A[N], B[N];int d[N], f[N][25], maxd, t;struct edgenode {    int to, next;}edge[M];set
      
        st;queue
       
         Q;void addedge(int u, int v) {    edge[tot].to = v;    edge[tot].next = head[u];    head[u] = tot++;}void bfs() {    while(!Q.empty()) Q.pop();    Q.push(1); d[1] = 1;    while(!Q.empty()) {        int tmp = Q.front(); Q.pop();        for(int i = head[tmp]; i != -1; i = edge[i].next) {            int v = edge[i].to;            if(d[v] != 0) continue;            d[v] = d[tmp] + 1;            f[v][0] = tmp;            for(int j = 1; j <= t; j++) f[v][j] = f[f[v][j - 1]][j - 1];            Q.push(v);        }    }}int Find(int x, int dep) {    if(d[x] < dep) return -1;    if(d[x] == dep) return x;    for(int i = t; i >= 0; i--) if(d[f[x][i]] >= dep) x = f[x][i];    return x;}bool judge(int x) {    st.clear();    for(int i = 1; i <= k1; i++) {        int fa = Find(A[i], x);        if(fa != -1) st.insert(fa);    }    for(int i = 1; i <= k2; i++) {        int fa = Find(B[i], x);        if(st.find(fa) != st.end()) return true;    }    return false;}int calc(int L, int R) {    int res = L;    while(L <= R) {        int Mid = (L + R) / 2;        if(judge(Mid)) res = max(res, Mid), L = Mid + 1;        else R = Mid - 1;    }    return res;}int main() {    while(scanf("%d%d", &n, &m) != EOF){        tot = 0;        memset(head, -1, sizeof head);        memset(f, 0, sizeof f);        memset(d, 0, sizeof d);        for(int i = 1, x, y; i <= n - 1; i++) {            scanf("%d%d", &x, &y);            addedge(x, y);            addedge(y, x);        }        t = (int)(log(n) / log(2)) + 1;        bfs();        while(m--) {            maxd = 1;            scanf("%d", &k1);            for(int i = 1; i <= k1; i++) scanf("%d", &A[i]), maxd = max(maxd, d[A[i]]);            scanf("%d", &k2);            for(int i = 1; i <= k2; i++) scanf("%d", &B[i]);            printf("%d\n", calc(1, maxd));        }    }    return 0;}
       
      
     

忘了多组读入痛失1A...