题意
给定一棵树，每次询问给出 \(k\) 个点。
问最少删除多少个 节点 (不能删这 \(k\) 个点) 使得这 \(k\) 个点两两不连通。
Sol
无解的情况是 \(trivial\) 的。
判断是否有相邻的两个关键点就行了。
但是 \(dp\) 是不太 \(trivial\) 的。
设 \(f_u\) 表示使得 \(u\) 子树内的关键点两两不连通需要的最小代价。
考虑讨论当前节点是否为关键点。
发现转移时缺少一个重要信息：
如果当前点不是关键点，且儿子内只有一个儿子子树内有关键点，此时删除儿子或者当前点都是错误的。
所以我们考虑设 \(g_u = 1/0\) 表示当前点是否与关键点相连。
\[f_u = \begin{cases}
vis_u = 1 & f_u = \sum g_v + f_v, g_u = 1 \cr
vis_u = 0, \sum g_v \le 1 & f_u = \sum f_v, g_u = \sum g_v \cr
vis_u = 0, \sum g_v > 1 & f_u = 1 + \sum f_v. g_u = 0
\end{cases}
\]
简单得到 \(n ^ 2\) 算法。
优化成 \(O(n \log n)\) 只需要套一个虚树就可以了。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <vector>
#include <bitset>
#define int long long
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
#define fi first
#define se second
const int N = 1e5 + 5, M = 2e5 + 5;
namespace G {
array <int, N> fir;
array <int, M> nex, to;
int cnt;
void add(int x, int y) {
cnt++;
nex[cnt] = fir[x];
to[cnt] = y;
fir[x] = cnt;
}
}
namespace T {
array <int, N> fir;
array <int, M> nex, to;
int cnt;
void add(int x, int y) {
cnt++;
nex[cnt] = fir[x];
to[cnt] = y;
fir[x] = cnt;
}
}
namespace Hpt {
using G::fir; using G::nex; using G::to;
array <int, N> son, siz, fa, dep;
void dfs1(int x) {
siz[x] = 1;
for (int i = fir[x]; i; i = nex[i]) {
if (to[i] == fa[x]) continue;
fa[to[i]] = x;
dep[to[i]] = dep[x] + 1;
dfs1(to[i]);
siz[x] += siz[to[i]];
if (siz[to[i]] > siz[son[x]]) son[x] = to[i];
}
}
array <int, N> dfn, idx, top;
int cnt;
void dfs2(int x, int Mgn) {
cnt++;
dfn[x] = cnt;
idx[cnt] = x;
top[x] = Mgn;
if (son[x]) dfs2(son[x], Mgn);
for (int i = fir[x]; i; i = nex[i]) {
if (to[i] == fa[x] || to[i] == son[x]) continue;
dfs2(to[i], to[i]);
}
}
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dfn[top[x]] < dfn[top[y]]) swap(x, y);
x = fa[top[x]];
}
if (dfn[x] > dfn[y]) swap(x, y);
return x;
}
}
namespace Vit {
vector <pii> isl;
array <int, N> stk;
int top;
void build() {
sort(isl.begin(), isl.end());
T::fir[isl[0].se] = 0; stk[top = 1] = isl[0].se;
for (int i = 1; i < (int)isl.size(); i++) {
pii x = isl[i]; int lcA = Hpt::lca(stk[top], x.se);
if (lcA != stk[top]) {
while (Hpt::dfn[stk[top - 1]] > Hpt::dfn[lcA])
T::add(stk[top - 1], stk[top]), top--;
if (stk[top - 1] != lcA)
T::fir[lcA] = 0, T::add(lcA, stk[top]), stk[top] = lcA;
else
T::add(stk[top - 1], stk[top]), top--;
}
T::fir[x.se] = 0, top++, stk[top] = x.se;
}
for (int i = 1; i < top; i++)
T::add(stk[i], stk[i + 1]);
}
bitset <N> vis;
pii dfs(int x) {
pii res(0, 0);
int tp1 = 0, tp2 = 0;
for (int i = T::fir[x]; i; i = T::nex[i]) {
pii now = dfs(T::to[i]);
tp1 += now.fi, tp2 += now.se;
}
if (vis[x]) res.fi = tp1 + tp2, res.se = 1;
else if (tp2 > 1) res.fi = 1 + tp1, res.se = 0;
else res.fi = tp1, res.se = (bool)tp2;
return res;
}
}
signed main() {
int n = read();
for (int i = 2; i <= n; i++) {
int x = read(), y = read();
G::add(x, y), G::add(y, x);
}
Hpt::dfs1(1), Hpt::dfs2(1, 0);
int q = read();
while (q--) {
int k = read();
Vit::isl.clear();
bool flg = 0; T::cnt = 0;
for (int i = 1; i <= k; i++) {
int x = read();
Vit::isl.push_back(make_pair(Hpt::dfn[x], x));
}
for (auto x : Vit::isl) Vit::vis[x.se] = 1;
for (auto x : Vit::isl) flg |= Vit::vis[Hpt::fa[x.se]];
Vit::build();
if (flg) puts("-1");
else write(Vit::dfs(Vit::stk[1]).fi), puts("");
for (auto x : Vit::isl) Vit::vis[x.se] = 0;
}
return 0;
}
```## 题意
给定一棵树，每次询问给出 $k$ 个点。
问最少删除多少个 **节点** (不能删这 $k$ 个点) 使得这 $k$ 个点两两不连通。
## Sol
无解的情况是 $trivial$ 的。
判断是否有相邻的两个关键点就行了。
但是 $dp$ 是不太 $trivial$ 的。
设 $f_u$ 表示使得 $u$ 子树内的关键点两两不连通需要的最小代价。
考虑讨论当前节点是否为关键点。
发现转移时缺少一个重要信息：
如果当前点不是关键点，且儿子内只有一个儿子子树内有关键点，此时删除儿子或者当前点都是错误的。
所以我们考虑设 $g_u = 1/0$ 表示当前点是否与关键点相连。
$$
f_u = \begin{cases}
vis_u = 1 & f_u = \sum g_v + f_v, g_u = 1 \cr
vis_u = 0, \sum g_v \le 1 & f_u = \sum f_v, g_u = \sum g_v \cr
vis_u = 0, \sum g_v > 1 & f_u = 1 + \sum f_v. g_u = 0
\end{cases}
$$
简单得到 $n ^ 2$ 算法。
优化成 $O(n \log n)$ 只需要套一个虚树就可以了。
## Code
``` cpp
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <vector>
#include <bitset>
#define int long long
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
#define fi first
#define se second
const int N = 1e5 + 5, M = 2e5 + 5;
namespace G {
array <int, N> fir;
array <int, M> nex, to;
int cnt;
void add(int x, int y) {
cnt++;
nex[cnt] = fir[x];
to[cnt] = y;
fir[x] = cnt;
}
}
namespace T {
array <int, N> fir;
array <int, M> nex, to;
int cnt;
void add(int x, int y) {
cnt++;
nex[cnt] = fir[x];
to[cnt] = y;
fir[x] = cnt;
}
}
namespace Hpt {
using G::fir; using G::nex; using G::to;
array <int, N> son, siz, fa, dep;
void dfs1(int x) {
siz[x] = 1;
for (int i = fir[x]; i; i = nex[i]) {
if (to[i] == fa[x]) continue;
fa[to[i]] = x;
dep[to[i]] = dep[x] + 1;
dfs1(to[i]);
siz[x] += siz[to[i]];
if (siz[to[i]] > siz[son[x]]) son[x] = to[i];
}
}
array <int, N> dfn, idx, top;
int cnt;
void dfs2(int x, int Mgn) {
cnt++;
dfn[x] = cnt;
idx[cnt] = x;
top[x] = Mgn;
if (son[x]) dfs2(son[x], Mgn);
for (int i = fir[x]; i; i = nex[i]) {
if (to[i] == fa[x] || to[i] == son[x]) continue;
dfs2(to[i], to[i]);
}
}
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dfn[top[x]] < dfn[top[y]]) swap(x, y);
x = fa[top[x]];
}
if (dfn[x] > dfn[y]) swap(x, y);
return x;
}
}
namespace Vit {
vector <pii> isl;
array <int, N> stk;
int top;
void build() {
sort(isl.begin(), isl.end());
T::fir[isl[0].se] = 0; stk[top = 1] = isl[0].se;
for (int i = 1; i < (int)isl.size(); i++) {
pii x = isl[i]; int lcA = Hpt::lca(stk[top], x.se);
if (lcA != stk[top]) {
while (Hpt::dfn[stk[top - 1]] > Hpt::dfn[lcA])
T::add(stk[top - 1], stk[top]), top--;
if (stk[top - 1] != lcA)
T::fir[lcA] = 0, T::add(lcA, stk[top]), stk[top] = lcA;
else
T::add(stk[top - 1], stk[top]), top--;
}
T::fir[x.se] = 0, top++, stk[top] = x.se;
}
for (int i = 1; i < top; i++)
T::add(stk[i], stk[i + 1]);
}
bitset <N> vis;
pii dfs(int x) {
pii res(0, 0);
int tp1 = 0, tp2 = 0;
for (int i = T::fir[x]; i; i = T::nex[i]) {
pii now = dfs(T::to[i]);
tp1 += now.fi, tp2 += now.se;
}
if (vis[x]) res.fi = tp1 + tp2, res.se = 1;
else if (tp2 > 1) res.fi = 1 + tp1, res.se = 0;
else res.fi = tp1, res.se = (bool)tp2;
return res;
}
}
signed main() {
int n = read();
for (int i = 2; i <= n; i++) {
int x = read(), y = read();
G::add(x, y), G::add(y, x);
}
Hpt::dfs1(1), Hpt::dfs2(1, 0);
int q = read();
while (q--) {
int k = read();
Vit::isl.clear();
bool flg = 0; T::cnt = 0;
for (int i = 1; i <= k; i++) {
int x = read();
Vit::isl.push_back(make_pair(Hpt::dfn[x], x));
}
for (auto x : Vit::isl) Vit::vis[x.se] = 1;
for (auto x : Vit::isl) flg |= Vit::vis[Hpt::fa[x.se]];
Vit::build();
if (flg) puts("-1");
else write(Vit::dfs(Vit::stk[1]).fi), puts("");
for (auto x : Vit::isl) Vit::vis[x.se] = 0;
}
return 0;
}