BZOJ2286 [SDOI2011]消耗战

题目大意

给你一颗树，树上每条边有边权，M次操作，每次从树上选出K个点，请选择一些边使得选定的每个点到1号点的路径上都至少经过一个点。求最小的总边长。

选出的总点数$\le 500000$

首先这道题多次询问一棵树的性质，显然即使有每次$O(n)$的树形DP解法也是不现实的。所以需要进行优化。

因为选出的点个数满足O(选定点个数)的算法可过，所以有一个大胆的想法：构建一颗新树——保留树上可用信息的同时删除冗余信息，构建的时间复杂度为O(选定点个数)就可以满足条件了。

这就是虚树。

以本题为例，求出所选点和他们之间两两的LCA(易知可以通过求相邻两点LCA的方式求出所有可能的LCA)，之后之间连边权值大小为路径上最小边(贪心删除最小的是最优策略)，之后跑树形DP就可以了。

具体实现看代码，Sengxian聚聚的博客讲解得非常好。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define R register
#define N 250010
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;
int rk[N],cnt,depth[N],fa[N][20],dis[N][20],lg[N],p[N],st[N],top;
int to[N<<2],val[N<<1],nxt[N<<2],head[N],headb[N],tot,totb,pt[N<<1];
long long f[N];
bool v[N];
inline void AE(R int X,R int Y,R int Z){to[++tot]=Y,val[tot]=Z,nxt[tot]=head[X],head[X]=tot;}
inline void AE(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];}
inline int LCA(R int X,R int Y)
{
	if(depth[X]>depth[Y]) swap(X,Y);
	for(int i=lg[n];~i;i--) if(depth[fa[Y][i]]>=depth[X]) Y=fa[Y][i];
	for(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];
}
inline long long getdis(R int X,R int Y)
{
	if(X==Y) return 0;
	int ret=0x3f3f3f3f;
	if(depth[X]>depth[Y]) swap(X,Y);
	for(int i=lg[n];~i;i--) if(depth[fa[Y][i]]>=depth[X]) ret=min(ret,dis[Y][i]),Y=fa[Y][i];
	for(int i=lg[n];~i;i--) if(fa[X][i]!=fa[Y][i]) ret=min(ret,dis[X][i]),ret=min(ret,dis[Y][i]),X=fa[X][i],Y=fa[Y][i];
	if(X!=Y) ret=min(ret,dis[X][0]),ret=min(ret,dis[Y][0]);
	return ret;
}
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],dis[pos][i]=min(dis[pos][i-1],dis[fa[pos][i-1]][i-1]);
	for(R int i=head[pos];i;i=nxt[i]) if(to[i]!=pre) fa[to[i]][0]=pos,dis[to[i]][0]=val[i],depth[to[i]]=depth[pos]+1,init(to[i],pos);
}
void DP(R int pos,R int pre)
{
	f[pos]=0;
	if(!v[pos]) {for(R int i=headb[pos];i;i=nxt[i])if(to[i]!=pre) DP(to[i],pos),f[pos]+=min(f[to[i]],getdis(pos,to[i]));}
	else f[pos]=0x3f3f3f3f;
	return;
}
int main()
{
	R int m,A,B,C,K;
	n=RI();
	for(int i=2;i<=n;++i) A=RI(),B=RI(),C=RI(),AE(A,B,C),AE(B,A,C),lg[i]=lg[i>>1]+1;
	depth[0]=-1,init(1,0);
	m=RI();
	totb=tot;
	while(m--)
	{
		K=RI();
		for(R int i=1;i<=K;++i) p[i]=RI(),v[p[i]]=true;
		p[++K]=1;
		sort(p+1,p+K+1,cmp);
		st[top=1]=p[1];
		for(R int i=2;i<=K;++i)
		{
			int tmp=LCA(p[i-1],p[i]);pt[i]=tmp,C=0;
			while(top&&depth[st[top]]>depth[tmp]) AE(C,st[top]),AE(st[top],C),C=st[top--];
			if(st[top]==tmp) AE(st[top],C),AE(C,st[top]);
			if(depth[st[top]]<depth[tmp]) AE(tmp,C),AE(C,tmp),st[++top]=tmp;
			st[++top]=p[i];
		}
		for(R int i=1;i<top;++i) AE(st[i],st[i+1]),AE(st[i+1],st[i]);
		DP(1,0);
		printf("%lld\n",f[1]);
		for(R int i=1;i<=K;++i) v[p[i]]=false,headb[pt[i]]=headb[p[i]]=0;
		tot=totb;
	}
}