BZOJ 3611 [HEOI2014]大工程

题目大意

给你一棵树，每次选出K个点，求这K个点之间任意两点间距离的和，最小值和最大值。

构建一颗虚树，虚树中的边长为两点间距离，之后跑树形DP。

设$f_i$为i及其子树的任意两点间距离和，$g_i$为最小值，$h_i$为最大值，那么有

(totsize表示子树点数，maxlen表示i为结尾的不重复的链的最大长度，max2len为次长，minlen同理)

$$f_i = \prod\limits_{i \to j} (totsize - size_j) \times (f_j + dis(i,j))$$

$$g_i = \begin{cases} maxlen (\text{i为实际意义的点}) \ maxlen + mex2len (\text{i仅为LCA})\end{cases}$$

$$h_i = maxlen + mex2len$$

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define R register
#define N 1000010
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 RI()
{
	R int ret=0;R char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp^'0'),tmp=nc();
	return ret;
}
int n,k,rk[N],cnt,depth[N],p[N],pt[N],fa[N][20],lg[N],st[N],top,siz[N],sizp[N],totp;
int to[N<<2],nxt[N<<2],head[N],headb[N],tot,totb;
long long f,g[N],h[N],ming=1<<30,maxh;
bool v[N];
inline void AE(R int X,R int Y){to[++tot]=Y,nxt[tot]=head[X],head[X]=tot;}
inline void AEb(R int X,R int Y){if(!X||!Y) return;to[++tot]=Y,nxt[tot]=headb[X],headb[X]=tot;}
inline bool cmp(R int X,R int Y){return rk[X]<rk[Y];}
void init(R int pos,R int pre)
{
	rk[pos]=++cnt;
	for(R int i=1;i<=lg[n];++i) fa[pos][i]=fa[fa[pos][i-1]][i-1];
	for(R int i=head[pos];i;i=nxt[i]) if(to[i]!=pre) depth[to[i]]=depth[pos]+1,fa[to[i]][0]=pos,init(to[i],pos);
}
int LCA(R int X,R int Y)
{
	if(depth[X]>depth[Y]) swap(X,Y);
	for(R int i=lg[n];~i;i--) if(depth[fa[Y][i]]>=depth[X]) Y=fa[Y][i];
	for(R int i=lg[n];~i;i--) if(fa[X][i]!=fa[Y][i]) X=fa[X][i],Y=fa[Y][i];
	return X==Y?X:fa[X][0];
}
long long dis(R int X,R int Y)
{
	int tmp;
	long long ret=0;
	if(depth[X]>depth[Y]) swap(X,Y);
	for(R int i=lg[n];~i;i--) if(depth[fa[Y][i]]>=depth[X]) ret+=1<<i,Y=fa[Y][i];
	for(R int i=lg[n];~i;i--) if(fa[X][i]!=fa[Y][i]) ret+=1<<(i+1),X=fa[X][i],Y=fa[Y][i];
	if(X!=Y) ret+=2;
	return ret;
}
void DP(int pos,int pre)
{
	siz[pos]=1,sizp[pos]=v[pos];
	long long ga=1<<30,gb=1<<30,ha=0,hb=0,tmp;
	for(R int i=headb[pos];i;i=nxt[i]) if(to[i]!=pre)
	{
		DP(to[i],pos);
		siz[pos]+=siz[to[i]];
		sizp[pos]+=sizp[to[i]];
		tmp=dis(to[i],pos);
		if(g[to[i]]+tmp<ga) ga=g[to[i]]+tmp;
		else if(g[to[i]]+tmp<gb) gb=g[to[i]]+tmp;
		if(h[to[i]]+tmp>ha) ha=h[to[i]]+tmp;
		else if(h[to[i]]+tmp>hb) hb=h[to[i]]+tmp;
	}
	if(v[pos]) g[pos]=0,ming=min(ming,ga);
	else g[pos]=ga,ming=min(ming,ga+gb);
	h[pos]=ha+hb;
	maxh=max(maxh,ha+hb);
}
void getF(int pos,int pre)
{
	for(R int i=headb[pos];i;i=nxt[i]) if(to[i]!=pre)
	{
		getF(to[i],pos);
		f+=dis(to[i],pos)*sizp[to[i]]*(k-sizp[to[i]]);
	}
}
int main()
{
	R int X,Y,q;
	n=RI();
	for(R int i=2;i<=n;++i) X=RI(),Y=RI(),AE(X,Y),AE(Y,X),lg[i]=lg[i>>1]+1;
	totb=tot;
	depth[0]=-1,init(1,0);
	q=RI();
	while(q--)
	{
		f=0,ming=1<<30,maxh=0;
		k=RI();
		for(R int i=1;i<=k;++i) p[i]=RI(),v[p[i]]=true;
		sort(p+1,p+k+1,cmp);
		st[top=1]=p[1];
		for(R int i=2;i<=k;++i)
		{
			X=LCA(p[i-1],p[i]),pt[i]=X,Y=0;
			while(top&&depth[st[top]]>depth[X]) AEb(st[top],Y),AEb(Y,st[top]),Y=st[top--];
			if(st[top]==X) AEb(st[top],Y),AEb(Y,st[top]);
			if(depth[st[top]]<depth[X]) AEb(X,Y),AEb(Y,X),st[++top]=X;
			st[++top]=p[i];
		}
		for(R int i=2;i<=top;++i) AEb(st[i-1],st[i]),AEb(st[i],st[i-1]);
		DP(p[1],0);
		getF(p[1],0);
		printf("%lld %lld %lld\n",f,ming,maxh);
		for(R int i=1;i<=k;++i) v[p[i]]=false,headb[p[i]]=0,headb[pt[i]]=0;
		tot=totb;
	}
}