LOJ6514 - 「雅礼集训 2018 Day10」文明

本题有虚树做法,基本思想差不多,但个人感觉还是换根树剖清真一点 233。

定义一组询问的根节点为这组询问的一号节点。

一个点会对答案产生贡献,当且仅当这个点到这组节点的其他节点的距离大于等于这个节点到这组询问的根节点的距离。

假设当前我们做到根节点为 $ root $ ,当前节点为 $ u $ 的情况,找出这条路径的中点为 $ mid $ ,那么肯定不会对答案产生贡献的点即整颗树 $ root $ 为根节点时 $ mid $ 这个节点的整颗子树。就是一个简单的换根树剖,乱搞一下即可。

代码:

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
// =================================
// author: memset0
// date: 2019.01.03 12:08:20
// website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
namespace ringo {
template <class T> inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (f) x = -x;
}
template <class T> inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 5e5 + 10;
int n, m, u, v, t, rt, cnt, dis, mid, pos, left, right;
int fa[N], id[N], top[N], son[N], siz[N], wid[N], dep[N];
int tot = 2, hed[N], nxt[N << 1], to[N << 1];

inline void add_edge(int u, int v) {
nxt[tot] = hed[u], to[tot] = v, hed[u] = tot++;
nxt[tot] = hed[v], to[tot] = u, hed[v] = tot++;
}

void dfs1(int u) {
siz[u] = 1;
for (int i = hed[u], v = to[i]; i; i = nxt[i], v = to[i])
if (v != fa[u]) {
fa[v] = u, dep[v] = dep[u] + 1, dfs1(v), siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}

void dfs2(int u, int toppoint) {
top[u] = toppoint, id[u] = ++pos, wid[id[u]] = u;
if (siz[u] == 1) return;
dfs2(son[u], toppoint);
for (int i = hed[u], v = to[i]; i; i = nxt[i], v = to[i])
if (v != fa[u] && v != son[u]) dfs2(v, v);
}

struct node {
int l, r, mid;
int sum, tag;
} p[N << 2];

inline void pushup(int u, int x) {
p[u].tag = x, p[u].sum = x ? (p[u].r - p[u].l + 1) : 0;
}

inline void pushdown(int u) {
if (p[u].tag == -1 || p[u].l == p[u].r) return;
pushup(u << 1, p[u].tag), pushup(u << 1 | 1, p[u].tag), p[u].tag = -1;
}

void build(int u, int l, int r) {
p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1, p[u].tag = -1;
if (l == r) return;
build(u << 1, l, p[u].mid);
build(u << 1 | 1, p[u].mid + 1, r);
}

void modify(int u, int l, int r, int x) {
if (l > r) return;
pushdown(u);
if (p[u].l == l && p[u].r == r) return pushup(u, x);
if (r <= p[u].mid) modify(u << 1, l, r, x);
else if (l > p[u].mid) modify(u << 1 | 1, l, r, x);
else modify(u << 1, l, p[u].mid, x), modify(u << 1 | 1, p[u].mid + 1, r, x);
p[u].sum = p[u << 1].sum + p[u << 1 | 1].sum;
}

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

int jump(int u, int v) {
while (dep[u] - dep[top[u]] + 1 <= v) {
v -= dep[u] - dep[top[u]] + 1;
u = fa[top[u]];
}
return wid[id[u] - v];
}

void main() {
read(n), read(m);
for (int i = 1; i < n; i++) read(u), read(v), add_edge(u, v);
dep[1] = 1, dfs1(1), dfs2(1, 1), build(1, 1, n);
for (int i = 1; i <= m; i++) {
read(cnt), read(rt), modify(1, 1, n, 1);
for (int i = 2; i <= cnt; i++) {
read(u), t = lca(rt, u);
left = dep[rt] - dep[t] + 1, right = dep[u] - dep[t] + 1;
dis = left + right - 1, mid = dis >> 1;
if (mid < right) {
v = jump(u, mid - 1);
modify(1, id[v], id[v] + siz[v] - 1, 0);
} else {
v = jump(rt, dis - mid - 1);
modify(1, 1, id[v] - 1, 0);
modify(1, id[v] + siz[v], n, 0);
}
}
print(p[1].sum, '\n');
}
}

} signed main() { return ringo::main(), 0; }
Your browser is out-of-date!

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

×