RT,代码如下:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define maxn 1000005
using namespace std;
struct node
{
int v,next,val;
}tr[maxn<<1];
int n,q,k;
int tot,head[maxn];
int tp,stk[maxn],que[maxn],vis[maxn],fl[maxn],deg[maxn];
ll ans[3];
int mx[maxn],mn[maxn],dw[maxn];//mx[i]是以i的子链的最大值,dw[i]是边i的子节点个数
int idc,fa[maxn],dep[maxn],size[maxn],son[maxn],top[maxn],dfn[maxn],f[maxn][25];
bool cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
void add(int x,int y,int z)
{
tot++;
tr[tot].v=y;
tr[tot].val=z;
tr[tot].next=head[x];
head[x]=tot;
}
void dfs1(int x)
{
size[x]=1;
for(int t=head[x];t;t=tr[t].next)
{
int y=tr[t].v;
if(y==fa[x])continue;
fa[y]=x;
dep[y]=dep[x]+1;
dfs1(y);
size[x]+=size[y];
if(size[y]>size[son[x]])
son[x]=y;
}
}
void dfs2(int x,int tp)
{
dfn[x]=++idc;
top[x]=tp;
if(son[x])dfs2(son[x],tp);
for(int t=head[x];t;t=tr[t].next)
{
int y=tr[t].v;
if(y==fa[x]||y==son[x])continue;
dfs2(y,y);
}
}
void ready(int x)
{
for(int i=0;i<=20;++i)
f[x][i+1]=f[f[x][i]][i];
for(int t=head[x];t;t=tr[t].next)
{
int y=tr[t].v;
if(y==fa[x])continue;
f[y][0]=x;
ready(y);
}
}//预处理倍增数组
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
return y;
}//求lca
int dis(int x,int y)
{
int ret=0;
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;--i)
{
if(dep[f[x][i]]>=dep[y])
{
x=f[x][i];
ret+=(1<<i);
}
if(x==y)return ret;
}
for(int i=20;i>=0;--i)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
ret+=(1<<(i+1));
}
}
ret+=2;
return ret;
}//求两节点间距离
void clear()
{
memset(head,0,sizeof(head));
memset(tr,0,sizeof(head));
tot=0;
}
void insert(int x)
{
if(!tp)
{
stk[++tp]=x;
return;
}
int anc=lca(x,stk[tp]);
while((tp>1)&&(dep[anc]<dep[stk[tp-1]]))
{
add(stk[tp-1],stk[tp],dis(stk[tp-1],stk[tp]));
deg[stk[tp-1]]++;deg[stk[tp]]++;
tp--;
}
if(dep[anc]<dep[stk[tp]])
{
add(anc,stk[tp],dis(anc,stk[tp]));
deg[stk[tp]]++;deg[anc]++;
tp--;
}
if((!tp)||(stk[tp]!=anc))stk[++tp]=anc;
stk[++tp]=x;
}//单向边,建立虚树
void dfs3(int x,int lst)//lst记录上一次的边
{
mx[x]=0;mn[x]=0x3f3f3f3f;
for(int t=head[x];t;t=tr[t].next)
{
int y=tr[t].v,z=tr[t].val;
dw[t]=0;
dfs3(y,t);
dw[lst]+=dw[t];
if(fl[y])//y是关键点
{
if(fl[x])//x也是关键点
ans[1]=min((int)ans[1],z);
else
ans[1]=min((int)ans[1],(int)mn[x]+z);
mn[x]=min((int)mn[x],z);//更新最小值
}
else//y不是关键点
{
if(fl[x])//x是关键点
ans[1]=min((int)ans[1],(int)mn[y]+z);
else
ans[1]=min((int)ans[1],(int)mn[x]+mn[y]+z);
mn[x]=min((int)mn[x],(int)mn[y]+z);
}
ans[0]+=z*dw[t]*(k-dw[t]);
if(deg[x]>1||fl[x])
ans[2]=max((int)ans[2],(int)mx[x]+mx[y]+z);
mx[x]=max((int)mx[x],(int)mx[y]+z);//更新最大值
}
if(fl[x])dw[lst]++;
head[x]=0;
deg[x]=0;
}
void start()
{
tot=tp=0;
ans[0]=ans[2]=0;
ans[1]=0x3f3f3f3f;
scanf("%d",&k);
for(int i=1;i<=k;++i)
{
scanf("%d",&que[i]);
fl[que[i]]=1;
}
sort(que+1,que+1+k,cmp);//按照dfn排序
if(que[1]!=1)
stk[++tp]=1;
for(int i=1;i<=k;++i)
insert(que[i]);
while(--tp)
{
add(stk[tp],stk[tp+1],dis(stk[tp],stk[tp+1]));//建立虚树
deg[stk[tp]]++;deg[stk[tp+1]]++;
}
dfs3(1,0);
for(int i=1;i<=k;++i)
fl[que[i]]=0;
for(int i=1;i<=tot;++i)
dw[i]=0;
printf("%lld %lld %lld\n",ans[0],ans[1],ans[2]);
}
int main()
{
//freopen("P4103_5.in","r",stdin);
//freopen("P4103.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y,1);
add(y,x,1);
}
fa[1]=0;
dep[1]=1;
dfs1(1);
dfs2(1,1);
ready(1);
clear();
scanf("%d",&q);
for(int i=1;i<=q;++i)
start();
return 0;
}