#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define int long long
using namespace std;
const int N=2e6+5,inf=INT_MAX;
int n,q,k,as[N];
int dfn[N],idx,f[N][25],dep[N],st[N],top,siz[N],cur[N];
int ans1,ans2,ans3;
struct node{
int nxt,v;
}a[N<<1],na[N<<1];
int hd[N],tot,nhd[N],ntot;
int read()
{
int x=0;
char ch=getchar();
while(ch<'0' || ch>'9')ch=getchar();
while(ch>='0' && ch<='9'){x=x*10+ch-48;ch=getchar();}
return x;
}
void add_a(int u,int v)
{
a[++tot].v=v;
a[tot].nxt=hd[u];
hd[u]=tot;
}
void add_n(int u,int v)
{
na[++ntot].v=v;
na[ntot].nxt=nhd[u];
nhd[u]=ntot;
}
void dfs(int u,int fa)
{
dfn[u]=++idx;
dep[u]=dep[fa]+1;
for(int i=1;(1<<i)<=dep[u];i++)
f[u][i]=f[f[u][i-1]][i-1];
for(int i=hd[u];i;i=a[i].nxt)
{
int v=a[i].v;
if(v==fa)
continue;
f[v][0]=u;
dfs(v,u);
}
}
int lca(int x,int y)
{
if(dep[x]>dep[y])
swap(x,y);
for(int i=20;i>=0;i--)
if(dep[x]<=dep[y]-(1<<i))
y=f[y][i];
if(x==y)
return x;
for(int i=20;i>=0;i--)
{
if(f[x][i]==f[y][i])
continue;
else
x=f[x][i],y=f[y][i];
}
return f[x][0];
}
bool cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
pair<int,int> dfs1(int u,int las)
{
int max1=u,max2=-1,min1=inf,min2=inf,fl=cur[u],nxt=fl?u:las;
siz[u]=cur[u];
if(fl && las!=-1 && u!=las)
ans2=min(ans2,dep[u]-dep[las]);
if(fl)
min1=u;
for(int i=nhd[u];i;i=na[i].nxt)
{
int v=na[i].v;
pair<int,int> ret=dfs1(v,nxt);
if(ret.fi>max1)
max2=max1,max1=ret.fi;
else if(ret.fi>max2)
max2=ret.fi;
if(ret.se<min1)
min2=min1,min1=ret.se;
else if(ret.se<min2)
min2=ret.se;
siz[u]+=siz[v];
ans1+=(k-siz[v])*siz[v]*(dep[v]-dep[u]);
}
nhd[u]=0;
if(min1!=inf && min2!=inf)
ans2=min(ans2,dep[min1]-dep[u]+dep[min2]-dep[u]);
if(max2!=-1)
ans3=max(ans3,dep[max1]-dep[u]+dep[max2]-dep[u]);
return mp(max1,min1);
}
/*
10
2 1
3 2
4 1
5 2
6 4
7 5
8 6
9 7
10 9
1
3 2 5 4
*/
signed main()
{
freopen("test.in","r",stdin);
n=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
add_a(u,v),add_a(v,u);
}
dfs(1,0);
q=read();
while(q--)
{
k=read();
memset(cur,0,sizeof cur);
ntot=0;
for(int i=1;i<=k;cur[as[i]]=1,i++)
as[i]=read();
sort(as+1,as+1+k,cmp);
top=0;
st[++top]=as[1];
for(int i=2;i<=k;i++)
{
int u=as[i];
int l=lca(st[top],u);
while(1)
{
if(dep[l]>=dep[st[top-1]])
{
if(l!=st[top])
{
add_n(l,st[top]);
if(l!=st[top-1])
st[top]=l;
else
top--;
}
break;
}
else
{
add_n(st[top-1],st[top]);
top--;
}
}
st[++top]=u;
}
while(--top)
add_n(st[top],st[top+1]);
ans1=0,ans2=inf,ans3=0;
dfs1(st[1],cur[st[1]]?st[1]:-1);
printf("%lld %lld %lld\n",ans1,ans2,ans3);
}
return 0;
}
在第一个dfs的lca预处理中,我奇怪地在#7上re了,但是评测结果显示wa。#9,#10 tle,怀疑是跟#7一样是死循环,但被判断成tle。