bzoj 2286 消耗战

Posted on | Views:

虚树 + 树形 $dp$ .

  • 考虑最暴力的树形 $dp$.设 $f_u$ 表示使得子树 $u$ 中所有关键点都与 $1$ 断开的最小代价.
  • 那么对于 $u$ 的所有儿子 $v$ ,如果 $v$ 是关键点,代价为 $val(u,v)$ ,否则为 $min(val(u,v),f_v)$ .
  • $f_u$ 就是所有儿子的代价之和,最终答案即为 $f_1$ .
  • 这样暴力 $dp$ 是 $O(nm)$ 的,无法通过.但注意到关键点数目总和 $\sum k\leq 5\times 10^5$ ,所以可以使用 虚树 进行处理.
  • 虚树 就是新建出的一颗树,只保留原树中所有关键节点与它们所有的 $LCA$ ,而原图中其它的链被简化成边或点.
  • 这样一颗 虚树 的节点数目不会超过 $2k-1$.因为 $k$ 个关键节点所有不同的 $LCA$ 最多 $k-1$ 个.
  • 构造时,先在原树中预处理 $dfs$ 序,子树大小 $siz$ ,并预处理倍增数组,以快速查找 $LCA$ 以及一条链上最小边.
  • 然后将所有关键点加入一个数组中,按照 $dfs$ 序排序,再将相邻两个点的 $LCA$ 也放入数组中,再放入 $1$ .
  • 再按照 $dfs$ 序排序,去重,就得到了我们在虚树上的 $dfs$ 遍历顺序.按照这个顺序进行 $dfs$ ,判断下个点是继续$dfs$ 还是回溯回来,只需用预处理的 $dfs$ 序和 $siz$ 判断下个点是否在当前的子树中.
  • 在虚树上 $dfs$ 的同时像原来一样进行树形 $dp$ .不过虚树中两个点的边在原图中实际是一条链.在虚树中直接割断两个点的花费是连接这两个点的链上所有边的最小边权.用预处理的倍增数组进行查询即可.
  • 时间复杂度 $O(\sum klogk)$ .

开始写的时候预处理倍增数组居然没有按拓扑序,而是直接按照节点编号顺序处理.这样居然还能有 $90pts$ .出计数不好吗,非要出最优化让人水过去.

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=250010;
int ecnt,head[MAXN],to[MAXN<<1],nx[MAXN<<1],val[MAXN<<1];
inline void addedge(int u,int v,int w)
{
	++ecnt;
	to[ecnt]=v;
	val[ecnt]=w;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int n,m,k;
int tid=0,marked[MAXN];
int fa[MAXN][20],minc[MAXN][20];
void init()
{
	for(int i=1;i<=n;++i)
		for(int j=1;j<=19;++j)
		{
			fa[i][j]=fa[fa[i][j-1]][j-1];
			minc[i][j]=min(minc[i][j-1],minc[fa[i][j-1]][j-1]);
		}
}
int dfsidx=0,dfn[MAXN],siz[MAXN],dep[MAXN];
void dfs(int u,int f)
{
	siz[u]=1;
	dep[u]=dep[f]+1;
	dfn[u]=++dfsidx;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		fa[v][0]=u;
		minc[v][0]=val[i];
		dfs(v,u);
		siz[u]+=siz[v];
	}
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=19;i>=0;--i)
		if(dep[x]-(1<<i)>=dep[y])
			x=fa[x][i];
	if(x==y)
		return x;
	for(int i=19;i>=0;--i)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int minval(int x,int lca)
{
	int res=1e9;
	for(int i=19;i>=0;--i)
		if(dep[x]-(1<<i)>=dep[lca])
		{
			res=min(res,minc[x][i]);
			x=fa[x][i];
		}
	return res;
}
bool cmp(int x,int y)
{
	return dfn[x]<dfn[y];
}
int q[MAXN<<1],tot;
int id;
ll f[MAXN];
void dfs_vtree()
{
	int u=q[id];
	f[u]=1e18;
	ll res=0;
	while(1)
	{
		if(id==tot)
			break;
		if(dfn[q[id+1]]<=dfn[u]+siz[u]-1)
		{
			int v=q[++id];
			if(marked[v]==tid)
			{
				dfs_vtree();
				f[v]=minval(v,u);
			}
			else
			{
				dfs_vtree();
				f[v]=min(f[v],1LL*minval(v,u));
			}
			res+=f[v];
		}
		else
			break;
	}
	if(res)
		f[u]=min(f[u],res);
}
int main()
{
	n=read();
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read(),w=read();
		addedge(u,v,w);
		addedge(v,u,w);
	}
	dfs(1,0);
	init();
	m=read();
	while(m--)
	{
		tot=0;
		k=read();
		++tid;
		for(int i=1;i<=k;++i)
		{
			int x=read();
			marked[x]=tid;
			q[++tot]=x;
		}
		sort(q+1,q+1+tot,cmp);
		for(int i=1;i<k;++i)
			q[++tot]=LCA(q[i],q[i+1]);
		q[++tot]=1;
		sort(q+1,q+1+tot,cmp);
		tot=unique(q+1,q+1+tot)-q-1;
		id=1;
		dfs_vtree();
		printf("%lld\n",f[1]);
	}
	return 0;
}