题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3611
https://www.luogu.org/problemnew/show/P4103
虚树的边权就是两端点的 dep 差。
求最短边可以像求最长边一样记录一个 d2[ cr ] 表示 cr 到其子树里最近的关键点的距离。
可以用 vis[ ] 记录哪些点是关键点。在 DP 的 dfs 里清空数组真是舒服。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int Mx(int a,int b){return a>b?a:b;}
int Mn(int a,int b){return a<b?a:b;}
const int N=1e6+,K=;
int n,hd[N],xnt,to[N<<],nxt[N<<];
int dep[N],dfn[N],tim,bin[K],pre[N][K];
bool cmp(int x,int y){return dfn[x]<dfn[y];}
void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
void dfs(int cr,int fa)
{
dfn[cr]=++tim;
dep[cr]=dep[fa]+; pre[cr][]=fa;
for(int t=;bin[t]<=dep[cr];t++)
pre[cr][t]=pre[pre[cr][t-]][t-];
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=fa) dfs(v,cr);
}
int get_lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
int d=dep[x]-dep[y];
for(int t=;bin[t]<=d;t++)
if(d&bin[t])x=pre[x][t];
if(x==y)return x;
for(int t=;t>=;t--)
if(pre[x][t]!=pre[y][t])
x=pre[x][t],y=pre[y][t];
return pre[x][];
}
namespace Tr{
int hd[N],xnt,to[N],nxt[N],len,mn; ll sm;
int p[N],tot,sta[N],top,siz[N],dis[N],d2[N];
bool vis[N];
void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
void dfs(int cr)
{
dis[cr]=; siz[cr]=vis[cr]; d2[cr]=(vis[cr]?:N);
for(int i=hd[cr],v;i;i=nxt[i])
{
dfs(v=to[i]); int w=dep[v]-dep[cr];
sm+=(ll)w*siz[v]*(tot-siz[v]);
len=Mx(len,dis[cr]+dis[v]+w); dis[cr]=Mx(dis[cr],dis[v]+w);
mn=Mn(mn,d2[cr]+d2[v]+w); d2[cr]=Mn(d2[cr],d2[v]+w);
siz[cr]+=siz[v];
}
vis[cr]=; hd[cr]=;
}
void solve()
{
tot=rdn(); xnt=;//xnt
for(int i=;i<=tot;i++)p[i]=rdn(),vis[p[i]]=;
sort(p+,p+tot+,cmp); sta[top=]=p[];//cmp!!!
for(int i=;i<=tot;i++)
{
int u=p[i], lca=get_lca(u,sta[top]);
while(top&&dfn[lca]<dfn[sta[top]])
{
if(dfn[sta[top-]]<dfn[lca])
add(lca,sta[top]);
else add(sta[top-],sta[top]);
top--;
}
if(sta[top]!=lca)sta[++top]=lca;
sta[++top]=u;
}
for(int i=;i<top;i++)add(sta[i],sta[i+]);
sm=; mn=N; len=;
dfs(sta[]); printf("%lld %d %d\n",sm,mn,len);
}
}
int main()
{
bin[]=;for(int i=;i<=;i++)bin[i]=bin[i-]<<;
n=rdn();
for(int i=,u,v;i<n;i++)
u=rdn(),v=rdn(),add(u,v),add(v,u);
dfs(,); int Q=rdn();
while(Q--)Tr::solve();
return ;
}