题解：
一道很水的虚树题。
每次建出虚树后跑一遍树形$dp$，状态比较多。
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N = 1000500; const ll Inf = 0x3f3f3f3f3f3f3f3fll; template<typename T> inline void read(T&x) { T f = 1,c = 0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} x = f*c; } int n,q,tl,hed[N],cnt,Hed[N],Cnt,sta[N],Sta[N],sum,Tl,rt; int use[N],vis[N]; struct EG { int to,nxt,w; }e[2*N],E[N]; void ae(int f,int t) { e[++cnt].to = t; e[cnt].nxt = hed[f]; hed[f] = cnt; } void aE(int f,int t,int w) { E[++Cnt].to = t; E[Cnt].nxt = Hed[f]; E[Cnt].w = w; Hed[f] = Cnt; } int dep[N],siz[N],top[N],fa[N],son[N],tin[N],tout[N],tim; void dfs1(int u,int f) { fa[u] = f; siz[u] = 1; dep[u] = dep[f]+1; for(int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; if(to==f)continue; dfs1(to,u); siz[u]+=siz[to]; if(siz[to]>siz[son[u]]) son[u]=to; } } void dfs2(int u,int Top) { top[u]=Top; tin[u]=++tim; if(son[u]) { dfs2(son[u],Top); for(int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; if(to!=fa[u]&&to!=son[u]) dfs2(to,to); } } tout[u]=tim; } int get_lca(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); x = fa[top[x]]; } return dep[x]<dep[y]?x:y; } bool cmp1(int x,int y){return tin[x]<tin[y];} bool check(int x,int y){return tin[x]<tin[y]&&tout[x]>=tout[y];} ll dp[N][6];//siz sum min max void dfs(int u) { ll minw,maxw; if(use[u]) { dp[u][0] = 1; dp[u][1] = 0; minw = 0; dp[u][2] = Inf; maxw = 0; dp[u][3] = 0; dp[u][4] = 0; dp[u][5] = 0; }else { dp[u][0] = 0; dp[u][1] = 0; minw = Inf; dp[u][2] = Inf; maxw = 0; dp[u][3] = 0; dp[u][4] = Inf; dp[u][5] = 0; } for(int j=Hed[u];j;j=E[j].nxt) { int to = E[j].to; dfs(to); dp[u][0]+=dp[to][0]; dp[u][1]+=dp[to][1]+E[j].w*dp[to][0]*(sum-dp[to][0]); dp[u][2]=min(dp[u][2],min(dp[to][2],minw+dp[to][4]+E[j].w)); dp[u][3]=max(dp[u][3],max(dp[to][3],maxw+dp[to][5]+E[j].w)); dp[u][4]=min(dp[u][4],dp[to][4]+E[j].w); dp[u][5]=max(dp[u][5],dp[to][5]+E[j].w); minw = min(minw,dp[to][4]+E[j].w); maxw = max(maxw,dp[to][5]+E[j].w); } } int main() { // freopen("tt.in","r",stdin); read(n); for(int u,v,i=1;i<n;i++) { read(u),read(v); ae(u,v),ae(v,u); } dfs1(1,0),dfs2(1,1); read(q); for(int i=1;i<=q;i++) { read(tl);sum=tl; for(int x,j=1;j<=tl;j++) read(x),sta[j]=x,vis[x]=use[x]=1; sort(sta+1,sta+1+tl,cmp1); for(int j=1,lim=tl;j<lim;j++) { int Lca = get_lca(sta[j],sta[j+1]); if(!vis[Lca]) vis[Lca]=1,sta[++tl]=Lca; } sort(sta+1,sta+1+tl,cmp1); for(int j=1;j<=tl;j++) { while(Tl&&!check(Sta[Tl],sta[j]))Tl--; if(!Tl)rt=sta[j]; else aE(Sta[Tl],sta[j],dep[sta[j]]-dep[Sta[Tl]]); Sta[++Tl]=sta[j]; } dfs(rt); printf("%lld %lld %lld ",dp[rt][1],dp[rt][2],dp[rt][3]); Cnt=Tl=0; for(int j=1;j<=tl;j++) { int v = sta[j]; use[v]=vis[v]=0; Hed[v]=0; } } return 0; }