发现可以直接建立虚树。
设 \(dp_{u,0/1/2}\) 表示第 \(u\) 个节点的子树内，所有选中节点到它的距离之和/选中节点中到它的最短距离/选中节点中到它的最长距离，\(as_{u,0/1/2}\) 则代表对于这个子树，题目所问问题的三个答案，\(i1,i2\) 分别为使 \(dp_{u,1/2}\) 取极值的 \(v\)。
则 \(dp\) 方程为：
\[dp_{u,0}=\sum\limits_{v\in uson}dis(u,v)\times sz_v+dp_{0,v} \]\[dp_{u,1}=\min\limits_{v\in uson}dp_{v,1}+dis(u,v) \]\[dp_{u,2}=\max\limits_{v\in uson}dp_{v,2}+dis(u,v) \]\[as_{u,0}=\sum\limits_{v\in uson}as_{v,0}+(dis(u,v)\times sz_v+dp_{v,0})(sz_x-sz_y) \]\[as_{u,1}=\min(\min\limits_{v\in uson}as_{v,1},\min\limits_{v\in uson且i1\ne v}dp_{u,1}+dp_{v,1}+dis(u,v)) \]\[as_{u,2}=\max(\max\limits_{v\in uson}as_{v,2},\max\limits_{v\in uson且i2\ne v}dp_{u,2}+dp_{v,2}+dis(u,v)) \]时间复杂度 \(O(\sum k\log k)\)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1000005;
int n,l,q,dfn[N],fa[N][21],p[N],a[N];
int m,r,t,k,h[N],nxt[N*2],to[N*2];
int d[N],nex[N*2],go[N*2],dep[N],b[N*2];
ll dp[3][N],as[3][N],c[N*2],sz[N];
int cmp(int x,int y){
return dfn[x]<dfn[y];
}void ad(int x,int y){
to[++m]=y;nxt[m]=h[x];h[x]=m;
}void add(int x,int y,int z){
go[++r]=y;c[r]=z;
nex[r]=d[x];d[x]=r;
}void dfs(int x,int f){
dep[x]=dep[f]+1;
fa[x][0]=f;dfn[x]=++l;
for(int i=0;i<20;i++)
fa[x][i+1]=fa[fa[x][i]][i];
for(int i=h[x];i;i=nxt[i])
if(f!=to[i]) dfs(to[i],x);
}int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;~i;i--)
if(dep[x]-dep[y]>=(1<<i))
x=fa[x][i];
if(x==y) return x;
for(int i=20;~i;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}int dis(int x,int y){
return dep[x]+dep[y]-2*dep[lca(x,y)];
}void dp_(int x,int f){
ll i1=0,i2=0;
as[1][x]=1e18;
if(p[x]==2) sz[x]=1;
else dp[1][x]=1e18;
for(int i=d[x];i;i=nex[i]){
int y=go[i];
if(y==f) continue;
dp_(y,x);sz[x]+=sz[y];
dp[0][x]+=c[i]*sz[y]+dp[0][y];
if(dp[1][x]>dp[1][y]+c[i])
dp[1][x]=dp[1][y]+c[i],i1=y;
if(dp[2][x]<dp[2][y]+c[i])
dp[2][x]=dp[2][y]+c[i],i2=y;
}if(p[x]==2) as[2][x]=dp[2][x];
for(int i=d[x];i;i=nex[i]){
int y=go[i];if(y==f) continue;
as[0][x]+=as[0][y]+(c[i]*sz[y]+dp[0][y])*(sz[x]-sz[y]);
as[1][x]=min(as[1][y],as[1][x]);
as[2][x]=max(as[2][y],as[2][x]);
if(i1!=y)
as[1][x]=min(as[1][x],dp[1][x]+dp[1][y]+c[i]);
if(i2!=y)
as[2][x]=max(as[2][x],dp[2][x]+dp[2][y]+c[i]);
}
}int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1,x,y;i<n;i++)
cin>>x>>y,ad(x,y),ad(y,x);
dfs(1,0);
cin>>q;while(q--){
cin>>k;
for(int i=1;i<=k;i++)
cin>>a[i],b[++t]=a[i],p[a[i]]=2;
sort(a+1,a+k+1,cmp);
for(int i=1;i<k;i++){
int x=lca(a[i],a[i+1]);
if(!p[x]) p[x]=1,b[++t]=x;
}sort(b+1,b+t+1,cmp);
for(int i=1;i<t;i++){
int lc=lca(b[i],b[i+1]);
add(lc,b[i+1],dep[b[i+1]]-dep[lc]);
add(b[i+1],lc,dep[b[i+1]]-dep[lc]);
}int rt=lca(b[1],b[2]);dp_(rt,0);
cout<<as[0][rt]<<" "<<as[1][rt]<<" "<<as[2][rt]<<"\n";
for(int i=1;i<=t;i++){
p[b[i]]=sz[b[i]]=d[b[i]]=0;
dp[0][b[i]]=dp[1][b[i]]=dp[2][b[i]]=0;
as[0][b[i]]=dp[1][b[i]]=as[2][b[i]]=0;
}for(int i=1;i<=r;i++)
nex[i]=go[i]=c[i]=0;
r=t=0;
}return 0;
}