去年省选的题。
突然发现还没有A这个题。
就抽时间写了写。
询问的那个树形dp很好搞。
我们把原树中有用的点(被选的点，和他们之间的lca)拿出来，建一棵虚树。
在虚树上dp就行了。
类似"消耗战"(为啥听着像卡组名)。
code:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int dep[1000005],dfn[1000005],tim;
int fa[1000005][21];
LL mn[1000005],mx[1000005],sum[1000005];
int Num[1000005];
bool mark[1000005];
LL Sum,Mn,Mx;
struct Graph{
int H[1000005],X[2000005],P[2000005],tot;
inline void add(int x,int y){
P[++tot]=y;X[tot]=H[x];H[x]=tot;
}
void dfs(int x){
dep[x]=dep[fa[x][0]]+1;
dfn[x]=++tim;
for(int i=H[x];i;i=X[i]){
if(P[i]!=fa[x][0]){
fa[P[i]][0]=x;
dfs(P[i]);
}
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=20;i>=0;i--){
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
void dp(int x){
if(mark[x]) mn[x]=0,mx[x]=0,sum[x]=0,Num[x]=1;
else mn[x]=0x3f3f3f3f3f3f3f3fLL,mx[x]=-0x3f3f3f3f3f3f3f3fLL,sum[x]=0,Num[x]=0;
for(int i=H[x];i;i=X[i]){
dp(P[i]);
mn[P[i]]+=dep[P[i]]-dep[x];
mx[P[i]]+=dep[P[i]]-dep[x];
sum[P[i]]+=Num[P[i]]*1LL*(dep[P[i]]-dep[x]);
if(mark[x]){
Mn=min(Mn,mn[P[i]]);
Mx=max(Mx,mx[x]+mx[P[i]]);
Mx=max(Mx,mx[P[i]]);
mx[x]=max(mx[x],mx[P[i]]);
Sum+=sum[x]*Num[P[i]]+sum[P[i]]*Num[x];
sum[x]+=sum[P[i]];
Num[x]+=Num[P[i]];
}else{
Mn=min(mn[x]+mn[P[i]],Mn);
mn[x]=min(mn[x],mn[P[i]]);
Mx=max(Mx,mx[x]+mx[P[i]]);
mx[x]=max(mx[x],mx[P[i]]);
Sum+=sum[x]*Num[P[i]]+sum[P[i]]*Num[x];
sum[x]+=sum[P[i]];
Num[x]+=Num[P[i]];
}
}
}
}tree,t;
bool cmp(int a,int b){
return dfn[a]<dfn[b];
}
int n,q,num;
int stk[1000005],top;
int a[1000005];
int use[1000005],cc;
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<n;i++){
scanf("%d%d",&x,&y);
tree.add(x,y);tree.add(y,x);
}
tree.dfs(1);
for(int j=1;j<=20;j++){
for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1];
}
scanf("%d",&q);
while(q--){
scanf("%d",&num);
cc=0;
for(int i=1;i<=num;i++){
scanf("%d",&a[i]);
mark[a[i]]=1;use[cc++]=a[i];
}
sort(a+1,a+num+1,cmp);
top=0;
if(!mark[1]){
use[cc++]=1;
}
stk[top++]=1;
for(int i=1;i<=num;i++){
int lca=tree.lca(a[i],stk[top-1]);
if(!mark[lca]) use[cc++]=lca;
while(dep[lca]<dep[stk[top-1]]){
if(dep[stk[top-2]]<=dep[lca]){
int x=stk[--top];
if(stk[top-1]!=lca){
stk[top++]=lca;
}
t.add(lca,x);
break;
}
t.add(stk[top-2],stk[top-1]);
top--;
}
if(stk[top-1]!=a[i]){
stk[top++]=a[i];
}
}
while(top>1) t.add(stk[top-2],stk[top-1]),top--;
Sum=0,Mn=0x3f3f3f3f3f3f3f3fLL,Mx=0;
t.dp(1);
printf("%lld %lld %lld\n",Sum,Mn,Mx);
t.tot=0;
for(int i=0;i<cc;i++) t.H[use[i]]=0,mark[use[i]]=0;
}
return 0;
}