[文章目录]
Description
国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。 我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了 k 个点，然后在它们两两之间 新建 C(k,2)条 新通道。现在对于每个计划，我们想知道：
1.这些新通道的代价和
2.这些新通道中代价最小的是多少
3.这些新通道中代价最大的是多少
虚树
建出虚树后进行树形DP即可，dp时注意只有输入的点能作为通道的端点。
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#define N 1001000
using namespace std;
const int inf=0x3f3f3f3f;
typedef long long ll;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int re=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
return re;
}
int n,k,head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
int dep[N],pos[N],rm[N<<1][22],Log[N<<1],tot;
void dfs(int x,int pre)
{
pos[x]=++tot; rm[tot][0]=x; dep[x]=dep[pre]+1;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
dfs(to[i],x),rm[++tot][0]=x;
}
inline int lca(int x,int y)
{
x=pos[x]; y=pos[y]; if(x>y) swap(x,y);
int lo=Log[y-x+1];
return dep[ rm[x][lo] ] < dep[ rm[y-(1<<lo)+1][lo] ]
? rm[x][lo] : rm[y-(1<<lo)+1][lo];
}
inline int dis(int x,int y) {return dep[x]+dep[y]-(dep[lca(x,y)]<<1);}
bool cmp(int x,int y){return pos[x]<pos[y];}
int z[N],d[N],Head[N],To[N<<1],Nxt[N<<1],f[N<<1],Cnt;
inline void Add(int x,int y)
{
int z=dis(x,y);
To[++Cnt]=y; Nxt[Cnt]=Head[x]; Head[x]=Cnt; f[Cnt]=z;
To[++Cnt]=x; Nxt[Cnt]=Head[y]; Head[y]=Cnt; f[Cnt]=z;
}
int siz[N],mx1[N],mx2[N],mi1[N],mi2[N];
bool vis[N];
ll ans1;
int ans2,ans3;
void Dfs(int x,int pre)
{
if(vis[x]) siz[x]=1,mi1[x]=0,mx1[x]=0;
else siz[x]=0,mi1[x]=inf,mx1[x]=-inf;
mi2[x]=inf,mx2[x]=-inf;
for(int i=Head[x];i;i=Nxt[i]) if(To[i]!=pre)
{
Dfs(To[i],x);
ans1+=(ll)f[i]*siz[To[i]]*(k-siz[To[i]]);
if(mi1[To[i]]+f[i]<=mi1[x]) mi2[x]=mi1[x],mi1[x]=mi1[To[i]]+f[i];
else if(mi1[To[i]]+f[i]<mi2[x]) mi2[x]=mi1[To[i]]+f[i];
if(mx1[To[i]]+f[i]>=mx1[x]) mx2[x]=mx1[x],mx1[x]=mx1[To[i]]+f[i];
else if(mx1[To[i]]+f[i]>mx2[x]) mx2[x]=mx1[To[i]]+f[i];
siz[x]+=siz[To[i]];
}
ans2=min(ans2,mi1[x]+mi2[x]); ans3=max(ans3,mx1[x]+mx2[x]); Head[x]=0;
}
int main()
{
n=read(); int i,j;
for(i=1;i<n;++i) add(read(),read());
dfs(1,0);
for(i=2;i<=tot;++i) Log[i]=Log[i>>1]+1;
for(i=1;i<=Log[tot];++i)
for(j=1;j+(1<<i)-1<=tot;++j)
rm[j][i]= (dep[ rm[j][i-1] ] < dep[ rm[j+(1<<(i-1))][i-1] ]
? rm[j][i-1] : rm[j+(1<<(i-1))][i-1]);
int m=read(),top,anc;
while(m--)
{
for(i=1;i<=k;++i) vis[d[i]]=0; Cnt=top=0;
for(k=read(),i=1;i<=k;++i) vis[d[i]=read()]=1;
sort(d+1,d+k+1,cmp); z[++top]=d[1];
for(i=2;i<=k;++i)
{
anc=lca(z[top],d[i]);
while(top>1&&dep[z[top-1]]>dep[anc]) Add(z[top],z[top-1]),top--;
if(anc!=z[top]) Add(z[top],anc); top--;
if(z[top]!=anc) z[++top]=anc; z[++top]=d[i];
}
while(top>1) Add(z[top],z[top-1]),top--;
ans1=0; ans2=inf; ans3=-inf;
Dfs(d[1],0);
printf("%lld %d %d\n",ans1,ans2,ans3);
}
return 0;
}