虚树

虚树一般解决如下问题:

在一棵树上给定一个点集$S$,求删除最少的非点集的点使得点集$S$中点两两互不联通(多次询问)

通常我们将点集$S$中的点称为关键点

可以发现,我们所有可以删除的点只跟所有关键点的$LCA$有关,于是就有了虚树这个概念

建树是用一个单调栈来维护的,保证只将所有与关键点及$LCA$的点加入虚树中

这里还有一个技巧,因为我们建新图使用$memset$复杂度会原地爆炸,只需要在遇见需要连边的点的时候将$begin[i]$清零即可

建完树后求解答案可以用贪心的思想:

对于当前点$i$,父亲为$fa$,$size[i]$表示$i$的子树内和$i$联通的关键点数

  • 如果$i$和$fa$均为关键点,无解
  • 如果$i$为关键点,且$size[i]>1$,说明$i$必须包含在答案内,则$size[i]=1$
  • 否则直接从下向上累加即可

$CF613D$是一道例题:

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
/***************************************************************
File name: CF613D.cpp
Author: ljfcnyali
Create time: 2019年08月09日 星期五 19时01分20秒
***************************************************************/
#include<bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for ( int i = (a), _end_ = (b); i <= _end_; ++ i )
#define mem(a) memset ( (a), 0, sizeof ( a ) )
#define str(a) strlen ( a )
typedef long long LL;

const int maxn = 400010;

int Begin[maxn], Next[maxn], To[maxn], e;
int n, m, q, dis[maxn], anc[maxn][20], dfn[maxn], cnt;
int a[maxn], size[maxn], ans[maxn], Stack[maxn], top;
bool vis[maxn];

inline void add(int u, int v) { To[++ e] = v; Next[e] = Begin[u]; Begin[u] = e; }

inline void DFS1(int u, int fa)
{
dfn[u] = ++ cnt;
for ( int i = Begin[u]; i; i = Next[i] )
{
int v = To[i]; if ( v == fa ) continue ;
dis[v] = dis[u] + 1; anc[v][0] = u;
DFS1(v, u);
}
}

inline int LCA(int x, int y)
{
if ( dis[x] < dis[y] ) swap(x, y);
for ( int j = 18; j >= 0; -- j ) if ( dis[anc[x][j]] >= dis[y] ) x = anc[x][j];
if ( x == y ) return x;
for ( int j = 18; j >= 0; -- j ) if ( anc[x][j] != anc[y][j] ) { x = anc[x][j]; y = anc[y][j]; }
return anc[x][0];
}

inline void Get_Tree()
{
Stack[top = 1] = 1; Begin[1] = 0;
REP(i, 1, m)
{
if ( a[i] == 1 ) continue ;
int fa = LCA(Stack[top], a[i]);
if ( fa != Stack[top] )
{
while ( dfn[Stack[top - 1]] > dfn[fa] )
{
add(Stack[top - 1], Stack[top]); -- top;
}
if ( dfn[Stack[top - 1]] != dfn[fa] ) { Begin[fa] = 0; add(fa, Stack[top]); Stack[top] = fa; }
else add(fa, Stack[top --]);
}
Begin[a[i]] = 0;
Stack[++ top] = a[i];
}
REP(i, 1, top - 1) add(Stack[i], Stack[i + 1]);
}

inline void DFS2(int u, int fa)
{
ans[u] = size[u] = 0;
for ( int i = Begin[u]; i; i = Next[i] )
{
int v = To[i]; if ( v == fa ) continue ;
DFS2(v, u);
ans[u] += ans[v]; size[u] += size[v];
}
if ( vis[u] ) ans[u] += size[u], size[u] = 1;
else if ( size[u] > 1 ) size[u] = 0, ++ ans[u];
}

inline int cmp(int x, int y) { return dfn[x] < dfn[y]; }

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%d", &n);
REP(i, 1, n - 1) { int u, v; scanf("%d%d", &u, &v); add(u, v); add(v, u); }
dis[1] = 1; DFS1(1, 0);
REP(j, 1, 18) REP(i, 1, n) anc[i][j] = anc[anc[i][j - 1]][j - 1];
scanf("%d", &q);
REP(o, 1, q)
{
scanf("%d", &m);
REP(i, 1, m) { scanf("%d", &a[i]); vis[a[i]] = true; }
REP(i, 1, m) if ( vis[anc[a[i]][0]] ) { puts("-1"); goto finish; }
sort(a + 1, a + m + 1, cmp);
Get_Tree();
DFS2(1, 0);
printf("%d\n", ans[1]);
finish: ;
REP(i, 1, m) vis[a[i]] = false;
}
return 0;
}