题目链接：

题意：

中文不解释。

题解：

比赛的时候是用的lca+贪心。

今天学了学虚树，这题实际就是求一个虚树的直径。

1 #include
      
         2 #define F(i,a,b) for(int i=(a);i<=(b);++i)  3 #define mst(a,b) memset(a,b,sizeof(a))  4 using namespace std;  5 typedef pair
       
        P;  6   7 const int N=3e5+7;  8 int in[N],out[N],ti,Dep[N];  9 namespace LCA 10 { 11     int g[N],v[N*2],nxt[N*2],ed,f[20][N*2]; 12     int idx[N],dep[N*2],vs[N*2],dfn; 13     void init(int n){ed=0,dfn=1;F(i,0,n)g[i]=0;} 14     void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;} 15     void dfs(int u=1,int fa=0,int d=0) 16     { 17         in[u]=++ti,Dep[u]=d; 18         idx[u]=dfn,vs[dfn]=u,dep[dfn++]=d; 19         for(int i=g[u];i;i=nxt[i])if(v[i]!=fa) 20         dfs(v[i],u,d+1),vs[dfn]=u,dep[dfn++]=d; 21         out[u]=ti; 22     } 23     void lca_init(int rt) 24     { 25         dfs(rt);F(i,1,dfn-1)f[0][i]=i; 26         for(int i=1;(1<
        
         
          y)x^=y,y^=x,x^=y; 37         int k=31-__builtin_clz(y-x+1); 38         int a=f[k][x],b=f[k][y-(1<
          
           G[N]; 47     void clear(int *a,int tot){F(i,1,tot)vis[a[i]]=vip[a[i]]=0,G[a[i]].clear();} 48     bool cmp(int x,int y){
    return in[x]
           
            out[q[t]])t--; 65 addedge(q[t],a[i]),q[++t]=a[i]; 66 } 67 return tot; 68 } 69 } 70 71 int n,m,x,y,num,a[N],mx[N]; 72 73 void dfs(int x,int fa,int val) 74 { 75 mx[x]=val; 76 for(auto &it:vtree::G[x]) 77 if(it.first!=fa) 78 dfs(it.first,x,val+it.second); 79 } 80 81 int main(){ 82 scanf("%d",&n); 83 F(i,2,n) 84 { 85 scanf("%d%d",&x,&y); 86 LCA::adg(x,y),LCA::adg(y,x); 87 } 88 LCA::lca_init(1),scanf("%d",&m); 89 F(i,1,m) 90 { 91 scanf("%d",&num); 92 F(j,1,num)scanf("%d",a+j); 93 num=vtree::build(a,num); 94 dfs(1,0,0); 95 int now,v=-1; 96 F(j,1,num)if(mx[a[j]]>v)now=a[j],v=mx[a[j]]; 97 dfs(now,0,0),v=-1; 98 F(j,1,num)if(vtree::vis[a[j]]) 99 {100 if(mx[a[j]]>v)v=mx[a[j]];101 }102 printf("%d\n",(v+1)/2);103 vtree::clear(a,num);104 }105 return 0;106 }