Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

虚树

Posted on

小清新优化思想。

是否有过这样的经历，一棵庞大的树，想到一个单次询问很牛的复杂度算法，但是树的大小太大，题目又毒瘤又多次询问，这时候你发现每次询问又只和一些点有关系，这时虚树就应需而生了。

简介

虚树就是在满足题目要求的情况下，将某一部分的节点抽出来，重新建立成一棵树，然后在上面进行原来的操作，从而以更小的复杂度，实现我们需要实现的操作。

建树

有两种建发，一种是用单调栈建，另一种使用排序建，这里使用从 p_b_p_b 那里学到的做法：

1
首先先将所有重要点按照dfn序排序，然后将每一个数和自己前缀的lca加入队列，再次按照dfn排序，这个时候每个点和自己前缀的lca就是自己在虚树中的父亲。

感觉起来挺对的，这一定能使所有点连成一棵树。

例题：CF613D Kingdom and its Cities

一句话题意：给你一颗树，每次选中一些点，让你删除最少的非选择点，使所有重要点不连通，问最少删除的点的数量。

$n \le 1e5,\sum k \le 1e5$。

看到这个数据范围，这个$\sum k$，果断在询问上下手脚。

观察这幅图：

image

我们发现左子树是完全没有必要遍历的，哪里啥都没有，所以我们考虑构造虚树，我们发现建立虚树之后每个重要节点删去所需代价没有变，所以正确性也是有保证的。

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

常数有点小大。

Code

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
#include<bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res), putchar('\n');
}
const int N = 3e5 + 5, Inf = 1e9;
int n, m, T;
int idx;
int e[N << 1], ne[N << 1], h[N], depth[N];
inline void add(int x, int y)
{
    idx ++;
    e[idx] = y, ne[idx] = h[x], h[x] = idx;
}
int dfn[N], cnt, lg[N << 1], f[N << 1][22], father[N], id[N];
int hh;
int a[N];
inline int lca(int x, int y)
{
    int l = id[x], r = id[y], len;
    if(l > r) swap(l, r);
    len = lg[r - l + 1];
    if(depth[f[l][len]] < depth[f[r - (1 << len) + 1][len]]) return f[l][len];
    return f[r - (1 << len) + 1][len];
}
int mark[N], type;
namespace dp{
    vector<int> edge[N];
    inline void init()
    {
        for(int i = hh, o;i >= 2;i --) 
        {
            o = lca(a[i], a[i - 1]);
            if(a[i] == o) continue;
            edge[o].push_back(a[i]);
        }
    }
    int dp(int x)
    {
        int res = 0, ans = 0, op;
        for(int i : edge[x])
        {
            if(depth[i] < depth[x]) continue;
            op = dp(i);
            ans += op;
            if(mark[x] && mark[i]) ans ++;
            else if(mark[i]) res ++;
        }
        if(res > 1) ans ++;
        if(res == 1) mark[x] = 1;
        return ans;
    }
}
inline bool cmp(int x, int y)
{
    return dfn[x] < dfn[y];
}
inline void work()
{
    read(m);
    hh = 0;
    for(int i = 1, o;i <= m;i ++) read(o), a[++ hh] = o, mark[o] = 1;
    for(int i = 1;i <= hh;i ++) 
        if(mark[father[a[i]]] && father[a[i]] != a[i])
        {
            for(int j = 1;j <= hh;j ++) mark[a[j]] = 0;
            return puts("-1"), void();
        }
    
    sort(a + 1, a + hh + 1, cmp);
    for(int i = hh, o;i >= 2;i --) 
    {
        o = lca(a[i], a[i - 1]);
        if(o == a[i] || o == a[i - 1]) continue;
        a[++ hh] = o;
    }
    sort(a + 1, a + hh + 1);
    hh = unique(a + 1, a + hh + 1) - (a + 1);
    sort(a + 1, a + hh + 1, cmp);
    dp:: init();
    write(dp:: dp(a[1]));
    for(int i = 1;i <= hh;i ++) dp:: edge[a[i]].clear(), mark[a[i]] = 0;
}
int now[N << 1], tot;
void dfs(int x, int y)
{
    depth[x] = depth[y] + 1;
    dfn[x] = ++ cnt, now[++ tot] = x, id[x] = tot, father[x] = y;
    for(int i = h[x], j; ~i;i = ne[i])
    {
        j = e[i];
        if(j == y) continue;
        dfs(j, x);
        now[++ tot] = x;
    }
}
inline void init()
{
    lg[1] = 0, lg[2] = 1;
    for(int i = 3;i <= tot;i ++) lg[i] = lg[i >> 1] + 1;
    for(int i = 1;i <= tot;i ++) f[i][0] = now[i];
    for(int j = 1;j < 22;j ++)
        for(int i = 1;i + (1 << j) - 1 <= tot;i ++)
        {
            if(depth[f[i][j - 1]] < depth[f[i + (1 << j - 1)][j - 1]]) f[i][j] = f[i][j - 1];
            else f[i][j] = f[i + (1 << j - 1)][j - 1];
        }
}
int main()
{
    memset(h, -1, sizeof(h));
    read(n);
    for(int i = 1, o, u;i < n;i ++) read(o, u), add(o, u), add(u, o);
    dfs(1, 1);
    init();
    read(T);
    while(T --) work();
    return 0;
}