「SDOI2011」消耗战 - 虚树+树形动规

题目大意

    给出一棵$n$个结点的树，每条边有一个切断所付出的代价，有$m$次询问，每次询问给出一个点集$K$，要求将点集与$1$结点分离，回答最小代价。
$\quad\quad2\le n\le 250000,m\ge1,\sum K\le500000$

---

题目分析

询问和点的数量太多了，我们没有办法对每个询问作出$\log n$的回答。

因为每次给出了点集，且对点集总数量有限制，考虑使用虚树降低时间复杂度。

对询问的点集建立虚树，那么我们就可以对其做暴力的树形动规了。

设状态$f[i]$表示将$i$为根的子树完全与$1$分离所需的最小代价。
若$i$有一个儿子是给出的点集中的一个，那么$f[i]=Min[i]$，否则$f[i]=\min(Min[i],\sum f[son])$。

其中$Min[i]$表示$i$到根路径上的边权最小值。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=250005;

int n,m,step,a[maxn],First[maxn],Last[maxn],p[maxn][25],Depth[maxn];
LL f[maxn],Min[maxn];

bool cmp(int a,int b) {
	return First[a]<First[b];
}

struct Edge {
	int from,to,dist;
};

vector<Edge>edges[maxn];
vector<int>tree[maxn];

void AddEdge(int x,int y,int v) {
	edges[x].push_back((Edge) {x,y,v});
}

void AddEdge(int x,int y) {
	tree[x].push_back(y);
}

void Dfs(int Now,int fa,int depth) {
	First[Now]=++step;
	Depth[Now]=depth;
	p[Now][0]=fa;
	for(int i=1; i<=log2(depth); i++)
		if(~p[Now][i-1])p[Now][i]=p[p[Now][i-1]][i-1];
		else break;
	for(Edge& e:edges[Now]) {
		int Next=e.to;
		if(Next==fa)continue;
		Min[Next]=min(Min[Now],(LL)e.dist);
		Dfs(Next,Now,depth+1);
	}
	Last[Now]=step;
}

int LCA(int a,int b) {
	if(Depth[a]<Depth[b])swap(a,b);
	int k=log2(Depth[a]);
	for(int i=k; i>=0; i--) {
		if(Depth[a]==Depth[b])break;
		if(Depth[a]-(1<<i)>=Depth[b])a=p[a][i];
	}
	if(a==b)return b;
	for(int i=k; i>=0; i--)
		if(p[a][i]!=-1&&p[a][i]!=p[b][i]) {
			a=p[a][i];
			b=p[b][i];
		}
	return p[a][0];
}

void build(vector<int>& a) {
	int tmp=a.size();
	for(int i=0; i<tmp-1; i++)a.push_back(LCA(a[i],a[i+1]));
	sort(a.begin(),a.end(),cmp);
	auto it=unique(a.begin(),a.end());
	a.erase(it,a.end());
	static int top=0,S[maxn];
	S[++top]=1;
	for(int now:a) {
		if(now==1)continue;
		while(top>=1) {
			if(First[now]>=First[S[top]]&&First[now]<=Last[S[top]]) {
				AddEdge(S[top],now);
				break;
			}
			top--;
		}
		if(S[top]!=now)S[++top]=now;
	}
}

void TreeDp(int Now) {
	f[Now]=Min[Now];
	LL sum=0;
	for(int Next:tree[Now]) {
		TreeDp(Next);
		sum+=f[Next];
	}
	if(!tree[Now].size())f[Now]=Min[Now]; //关键点只可能是叶子结点
	else f[Now]=min(f[Now],sum);
	tree[Now].clear(); //为下一次清空做准备
}

int main() {
	memset(p,-1,sizeof(p));
	n=Get_Int();
	for(int i=1; i<n; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		AddEdge(x,y,v);
		AddEdge(y,x,v);
	}
	Min[1]=1e18;
	Dfs(1,-1,1);
	m=Get_Int();
	for(int i=1; i<=m; i++) {
		int k=Get_Int();
		for(int j=1; j<=k; j++)a[j]=Get_Int();
		sort(a+1,a+k+1,cmp);
		vector<int>tmp;
		tmp.clear();
		tmp.push_back(a[1]);
		for(int j=2; j<=k; j++) //题目性质：只保留靠上的点
			if(!(First[a[j]]>=First[tmp.back()]&&First[a[j]]<=Last[tmp.back()]))tmp.push_back(a[j]);
		build(tmp);
		TreeDp(1);
		printf("%lld\n",f[1]);
	}
	return 0;
}