NKOJ 2654 （SDOI 2011）消耗战 （虚树+树形DP）

发表于 |
字数统计: 1,285字 | 阅读时长 ≈ 7min

P2654【SDOI2011第2轮DAY2】消耗战

问题描述

在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
　　侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。

输入格式

第一行一个整数n，代表岛屿数量。
接下来n-1行，每行三个整数u,v,w，代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连，保证1<=u,v<=n且1<=c<=100000。
第n+1行，一个整数m，代表敌方机器能使用的次数。

输出格式

输出有m行，分别代表每次任务的最小代价。

样例输入

10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6

样例输出

12
32
22

提示

对于10%的数据，2<=n<=10,1<=m<=5,1<=ki<=n-1
对于20%的数据，2<=n<=100,1<=m<=100,1<=ki<=min(10,n-1)
对于40%的数据，2<=n<=1000,m>=1,sigma(ki)<=500000,1<=ki<=min(15,n-1)
对于100%的数据，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1

此题是虚树的模板题，令$F[x]$表示将$x$和其子树中的能源点切断的最小代价，转移方程就是
$$F[x]=\sum dis(x,y),y有能源+\sum min(dis(x,y),F[y]),y没有能源$$
关键在于不能进行m次DP，注意到题目的特殊条件，构造虚树在虚树上DP即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 500005
#define ll long long
using namespace std;
int n,m,S=19,fa[N][20],dis[N][20];
int dfn[N],VT,dep[N],P[N],cnt,Q[N],top;
ll F[N];
int TOT,LA[N],NE[N],EN[N],LE[N];
int tot,la[N],ne[N],en[N],le[N];
bool mark[N];
bool cmp(int x,int y)
{return dfn[x]<dfn[y];}
void ADD(int x,int y,int z)
{
	TOT++;
	EN[TOT]=y;
	LE[TOT]=z;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void add(int x,int y,int z)
{
	tot++;
	en[tot]=y;
	le[tot]=z;
	ne[tot]=la[x];
	la[x]=tot;
}
void DFS(int x,int f)
{
	int i,y;
	dfn[x]=++VT;
	fa[x][0]=f;
	dep[x]=dep[f]+1;
	for(i=1;i<=S;i++)fa[x][i]=fa[fa[x][i-1]][i-1],dis[x][i]=min(dis[x][i-1],dis[fa[x][i-1]][i-1]);
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(y!=f)dis[y][0]=LE[i],DFS(y,x);
	}
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	int i,t=dep[x]-dep[y];
	for(i=0;i<=S;i++)
	if(t>>i&1)x=fa[x][i];
	if(x==y)return x;
	for(i=S;i>=0;i--)
	if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int Gdis(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	int i,t=dep[x]-dep[y],ans=1e9;
	for(i=0;i<=S;i++)
	if(t>>i&1)ans=min(ans,dis[x][i]),x=fa[x][i];
	return ans;
}
void BT()
{
	int i,j,k,lca;
	top=0;Q[++top]=1;
	for(i=1;i<=cnt;i++)
	{
		lca=LCA(P[i],Q[top]);
		if(dep[lca]==dep[Q[top]]){Q[++top]=P[i];continue;}
		while(dep[lca]<dep[Q[top-1]])
		{
			add(Q[top-1],Q[top],Gdis(Q[top],Q[top-1]));
			top--;
		}
		add(lca,Q[top],Gdis(lca,Q[top]));top--;
		if(Q[top]!=lca)Q[++top]=lca;
		Q[++top]=P[i];
	}
	while(--top)add(Q[top],Q[top+1],Gdis(Q[top],Q[top+1]));
}
void DP(int x)
{
	F[x]=0;int i,y;
	for(i=la[x];i;i=ne[i])
	{
		y=en[i];DP(y);
		if(mark[y])F[x]+=le[i];
		else F[x]+=min(1ll*le[i],F[y]);
		mark[y]=0;
	}
	la[x]=0;
}
int main()
{
	int i,j,k,x,y,z;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		ADD(x,y,z);ADD(y,x,z);
	}
	DFS(1,0);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d",&cnt);
		for(j=1;j<=cnt;j++)scanf("%d",&P[j]),mark[P[j]]=1;
		sort(P+1,P+cnt+1,cmp);tot=0;
		BT();DP(1);
		printf("%lld\n",F[1]);
	}
}