MMSet2(思维)

问题转化为找s集合中距离最远的两点的距离

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int n,m,he[maxn];
int read(){
    int x; scanf("%d",&x);
    return x;
}
struct edge{
    int to,nxt;
}d[maxn<<1]; int head[maxn<<1],cnt=1;
void add(int u,int v){
    d[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
int deep[maxn],fa[maxn][22],lg[maxn];
void dfs(int u,int father)
{
    deep[u]=deep[father]+1;
    fa[u][0]=father;
    for(int i=1;i<=lg[ deep[u] ];i++)
        fa[u][i]=fa[ fa[u][i-1] ][i-1];
    for(int i=head[u];i;i=d[i].nxt )
    {
        int v=d[i].to;
        if( v==father )    continue;
        dfs(v,u);
    }
}
int lca(int x,int y)
{
    if( deep[x]<deep[y] )    swap(x,y);
    while( deep[x]>deep[y] )
        x=fa[x][ lg[deep[x]-deep[y]]-1 ];
    if( x==y )    return x;
    for(int i=lg[ deep[x] ]-1;i>=0;i-- )
        if( fa[x][i]!=fa[y][i] )
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void init()
{
    for(int i=1;i<=n;i++)
        lg[i]=lg[i-1]+( (1<<lg[i-1])==i );
}
int main()
{
    n=read();
    init();
    for(int i=1;i<n;i++)
    {
        int l,r;
        l=read(),r=read();
        add(l,r); add(r,l);
    }
    dfs(1,0);
    int q; q=read();
    while( q-- )
    {
        int s=read();
        int shen=0,num=0,ans=0;
        for(int i=1;i<=s;i++)
        {
            he[i]=read();
            if( deep[ he[i] ]>shen )
                shen=deep[ he[i] ],num=he[i];
        }
        for(int i=1;i<=s;i++)
        {
            if( he[i]==num )    continue;
            int zu=lca(num,he[i] );
            int juli=deep[num]+deep[ he[i] ]-2*deep[zu];
            ans=max(ans,juli);
        }
        printf("%d\n",(ans+1)/2);
    }
}