MMSet2

将求树的直径的过程进行模拟即可~

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+50,M=20;
vector<int>v[N];
int dep[N],w[N],f[N][M];
void dfs(int u,int fa)
{
    dep[u]+=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<20;i++)    f[u][i]=f[f[u][i-1]][i-1];
    for(int x:v[u])
    {
        if(x!=fa)    dfs(x,u);
    }
}



int lca(int x,int y)
{
    if(dep[x]<dep[y])    swap(x,y);//假定x的深度更大.
    for(int i=19;i>=0;i--)
    {
        if(dep[f[x][i]]>=dep[y])    x=f[x][i];
    }if(x==y)    return x;
    for(int i=19;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])    x=f[x][i],y=f[y][i];
    }return f[x][0];
}

int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }dfs(1,0);
    int Q;scanf("%d",&Q);
    while(Q--)
    {
        int s,mx=0,point;scanf("%d",&s);
        for(int i=1;i<=s;i++)
        {
            scanf("%d",&w[i]);
            if(dep[w[i]]>mx) point=w[i],mx=dep[w[i]];
        }int ans=0;
        for(int i=1;i<=s;i++)
        {
            ans=max(ans,dep[w[i]]+dep[point]-2*dep[lca(w[i],point)]);
        }ans++;ans/=2;
        printf("%d\n",ans);
    }
    return 0;
}