「BZOJ 2286」「SDOI 2011」消耗战-虚树

一棵 $n$ 个点,边带权的树,$m$ 次询问,每次给出 $k$ 个关键点,求割掉最小代价的边使 $1$ 号点不能到达任何关键点。

链接

BZOJ 2286

题解

首先把边权下放到点上,直接 dp 是很显然的,$f(u) = \min{g(u), \sum f(v)}$,$v$ 是 $u$ 的子树,$g(u)$ 表示 $u$ 到 $1$ 路径上的最小权值,即表示断开 $u$ 与根节点的最小代价。

注意到数据范围,很显然要建虚树,然后在虚树上 dp,就可以了。

关于建虚树的过程,类似于建笛卡尔树的过程,都是用栈来维护右链,先把关键点按照 DFS 序排序,然后考虑顺序将关键点插入,为了方便我们先在栈中加入根节点。

用栈维护右链的过程,一开始,栈中只有根节点,当要加入点 $u$ 时,我们求出 $u$ 与栈顶元素 $v$ 的 $\text{lca}$,如果 $\text{lca} = v$,说明 $u$ 到 $v$ 是一条直链,此时直接将 $u$ 加入栈即可,右链被延长了;否则我们一直退栈,退到栈顶的第二个元素的深度比 $\text{lca}$ 小,并且在退栈的过程中连边,然后将其加入栈中。

时间复杂度 $O(k \log n)$。

代码

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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「BZOJ 2286」「SDOI 2011」消耗战 05-09-2017
* 虚树
* @author xehoth
*/
#include <bits/stdc++.h>

namespace IO {

inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return;
c == '-' ? iosig = true : 0;
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig ? x = -x : 0;
}

inline void read(char &c) {
while (c = read(), isspace(c) && c != -1)
;
}

inline int read(char *buf) {
register int s = 0;
register char c;
while (c = read(), isspace(c) && c != -1)
;
if (c == -1) {
*buf = 0;
return -1;
}
do
buf[s++] = c;
while (c = read(), !isspace(c) && c != -1);
buf[s] = 0;
return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
*oh++ = c;
}

template <typename T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
x < 0 ? (print('-'), x = -x) : 0;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
}
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }

struct InputOutputStream {
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(x);
return *this;
}

template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}

~InputOutputStream() { flush(); }
} io;
}

namespace {

using IO::io;

const int MAXN = 250000;

struct Node {
int v, w;

Node(int v, int w) : v(v), w(w) {}
};

template <typename T>
struct Graph {
typedef std::vector<T> Vector;
Vector edge[MAXN + 1];

inline void addEdge(const int u, const T &v) { edge[u].push_back(v); }

inline Vector &operator[](const int i) { return edge[i]; }

inline void clear(const int n) {
for (register int i = 0; i <= n; i++) edge[i].clear();
}
};

struct HeavyLightChainDecomposition {
Graph<Node> g;
typedef Graph<Node>::Vector::iterator Iterator;

int fa[MAXN + 1], dep[MAXN + 1], sz[MAXN + 1], w[MAXN + 1];
int top[MAXN + 1], son[MAXN + 1], dfn[MAXN + 1], idx;
bool vis[MAXN + 1];

inline void dfs1(const int u) {
vis[u] = true, sz[u] = 1, dep[u] = dep[fa[u]] + 1;
for (Iterator p = g[u].begin(); p != g[u].end(); p++) {
if (!vis[p->v]) {
fa[p->v] = u, w[p->v] = std::min(w[u], p->w);
dfs1(p->v);
sz[u] += sz[p->v], sz[p->v] > sz[son[u]] ? son[u] = p->v : 0;
}
}
}

inline void dfs2(const int u) {
vis[u] = false, dfn[u] = ++idx,
top[u] = (u == son[fa[u]] ? top[fa[u]] : u);
for (Iterator p = g[u].begin(); p != g[u].end(); p++)
if (p->v == son[u]) dfs2(p->v);
for (Iterator p = g[u].begin(); p != g[u].end(); p++)
if (vis[p->v]) dfs2(p->v);
}

inline int lca(int u, int v) {
while (top[u] != top[v])
dep[top[u]] < dep[top[v]] ? v = fa[top[v]] : u = fa[top[u]];
return dep[u] < dep[v] ? u : v;
}

inline void cut(int root = 1) { dfs1(root), dfs2(root); }

inline void init(const int n) {
for (register int i = 1, u, v, w; i < n; i++) {
io >> u >> v >> w;
g.addEdge(u, Node(v, w)), g.addEdge(v, Node(u, w));
}
w[1] = INT_MAX;
cut();
}
};

inline bool cmp(int, int);

struct VirtualTree {
#define long long long
HeavyLightChainDecomposition hld;

Graph<int> g;

typedef Graph<int>::Vector::iterator Iterator;

int *w, *dep, *dfn;

inline void addEdge(const int u, const int v) {
g.addEdge(u, v), g.addEdge(v, u);
}

inline int build(int *p, int n) {
std::sort(p, p + n, cmp);
register int cnt = 0;
for (register int i = 1; i < n; i++)
if (hld.lca(p[i], p[cnt]) != p[cnt]) p[++cnt] = p[i];
n = ++cnt;
static std::vector<int> st;
st.clear(), st.reserve(n), st.push_back(1), p[cnt++] = 1;
for (register int i = 0, u, lca; i < n; i++) {
u = p[i], lca = hld.lca(u, st.back());
if (lca == st.back()) {
st.push_back(u);
} else {
while (st.size() >= 2 && dep[*++st.rbegin()] >= dep[lca])
addEdge(*++st.rbegin(), st.back()), st.pop_back();
if (st.back() != lca)
addEdge(lca, st.back()), p[cnt++] = lca, st.back() = lca;
st.push_back(u);
}
}
for (register int i = 0; i < st.size() - 1; i++)
addEdge(st[i], st[i + 1]);
return cnt;
}

inline long dfs(int u, int v) {
register long ret = 0;
for (Iterator p = g[u].begin(); p != g[u].end(); p++)
if (*p != v) ret += std::min(dfs(*p, u), (long)w[*p]);
return ret ? ret : LLONG_MAX;
}

inline void solve() {
register int n;
io >> n, hld.init(n);
w = hld.w, dfn = hld.dfn, dep = hld.dep;
register int m, k;
io >> m;
static int a[MAXN + 1];
while (m--) {
io >> k;
for (register int i = 0; i < k; i++) io >> a[i];
k = build(a, k);
io << dfs(1, 0) << '\n';
for (register int i = 0; i < k; i++) g[a[i]].clear();
}
}
#undef long
} task;

inline bool cmp(const int u, const int v) { return task.dfn[u] < task.dfn[v]; }
}

int main() {
task.solve();
return 0;
}
# DP

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×