jzoj 5394(LCA)

对于一条链直接贪心区间选点问题。
把这个问题放到树上做。
贪心区间选点是尽量把点选到右边,那么树上思路也如此。
首先,DFS序中一条路径最后出现的节点一定是LCA
所以按照DFS序正序处理每一个点,如果这个点是某条路径的LCA并且这条路径没有被切,就切掉这条路径。
因为 假设一条路径LCA为$l$,所有 经过$l$的儿子的路径 都能经过$l$(这条路径中一定有一个点深度比$l$浅, 而这些路径的LCA的深度都比$l$的深度浅。所以我们要按照DFS序从下到上处理)。因此删除$l$是最划算的
做法可以是树链剖分维护区间和,支持区间查询和单点修改,用来维护一条路径上是否有断点(被切掉)。判断路径的时候可以用DFS序排序每条路径的LCA,然后顺序处理即可。
时间复杂度$O(klogk+klog^2n)$(排序+处理(树链剖分复杂度是$log^2n$))

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define LL long long
#define db double
#define FN2 "ping"
const int MAXN = 1000000 + 5;
int tb, n, m, k, dep[MAXN], top[MAXN], fa[MAXN], siz[MAXN], son[MAXN], p[MAXN], fdfsx[MAXN], dfsx[MAXN], dfstot = 0, ansqj[3 * MAXN];
vector<int> G[MAXN];
struct data {
int l, r, lca;
bool operator < (const data &b) const {
return fdfsx[lca] < fdfsx[b.lca];
}
}a[3 * MAXN];
void dfs1(int u, int pa) {
dep[u] = dep[pa] + 1, siz[u] = 1, fa[u] = pa;
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (v != pa) {
dfs1(v, u);
siz[u] += siz[v];
if (son[u] == -1 || siz[son[u]] < siz[v]) son[u] = v;
}
}
dfsx[++dfstot] = u;
}
void dfs2(int u, int chn) {
top[u] = chn, p[u] = ++tb;
if (son[u] != -1) {
dfs2(son[u], chn);
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (v != fa[u] && v != son[u]) dfs2(v, v);
}
}
}
#define lc (o << 1)
#define rc (o << 1 | 1)
#define M ((l + r) >> 1)
int sumv[MAXN * 4];
void build(int o, int l, int r) {
if (l == r) return ;
else sumv[l] = sumv[r] = 0, build(lc, l, M), build(rc, M + 1, r);
}
void pushup(int o) {
sumv[o] = sumv[lc] + sumv[rc];
}
void update(int o, int l, int r, int x, int v) {
if (l == r) sumv[o] = v; else {
if (x <= M) update(lc, l, M, x, v);
else if (M < x) update(rc, M + 1, r, x, v);
pushup(o);
}
}
int query(int o, int l, int r, int x, int y) {
if (x <= l && r <= y) {
return sumv[o];
}
int ret = 0;
if (x <= M) ret += query(lc, l, M, x, y);
if (M < y) ret += query(rc, M + 1, r, x, y);
return ret;
}
int findans(int u, int v) {
int ret = 0, f1 = top[u], f2 = top[v];
while (f1 != f2) {
if (dep[f1] < dep[f2]) swap(f1, f2), swap(u, v);
ret += query(1, 1, n, p[f1], p[u]);
u = fa[f1], f1 = top[u];
}
if (dep[u] < dep[v]) swap(u, v);
return ret + query(1, 1, n, p[v], p[u]);
}
int getlca(int u, int v) {
int f1 = top[u], f2 = top[v];
while (f1 != f2) {
if (dep[f1] < dep[f2]) swap(f1, f2), swap(u, v);
u = fa[f1], f1 = top[u];
}
if (dep[u] < dep[v]) swap(u, v);
return v;
}
void clean() {
tb = 0;
for (int i = 1; i <= n; i++) G[i].clear(), dep[i] = top[i] = fa[i] = siz[i] = p[i] = fdfsx[i] = dfsx[i] = 0, son[i] = -1;
}
void solve() {
clean();
for (int u, v, i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}//read edges
dfs1(1, 0), dfs2(1, 1);
build(1, 1, n);
for (int i = 1; i <= n; i++) fdfsx[dfsx[i]] = i;//chuli shulianpoufen
scanf("%d", &k);
for (int i = 1; i <= k; i++) {
scanf("%d%d", &a[i].l, &a[i].r);
a[i].lca = getlca(a[i].l, a[i].r);
}//read route
int ans = 0;
sort(a + 1, a + 1 + k);
for (int i = 1; i <= k; i++) {
int ret = findans(a[i].l, a[i].r);
if (ret == 0) update(1, 1, n, p[a[i].lca], 1), ansqj[++ans] = a[i].lca;
}
printf("%d\n", ans);
for (int i = 1; i <= ans; i++) printf("%d ", ansqj[i]);
}
int main() {
freopen(FN2".in", "r", stdin);freopen(FN2".out", "w", stdout);
scanf("%d%d", &n, &m), solve();
fclose(stdin), fclose(stdout);
return 0;
}

题目描述

Tgopknight所连接的网络共有n 个站点,由于经费问题,每两个站点之间有且仅有一条线
路,这些站点中有一些损坏了,Tgopknight进行了k次测试,每次测试两个站点之间是否连通,由
于Tgopknight 手太好,他每次测试的两个站点之间都不连通。Tgopknight 现在想知道最少有多少
个站点损坏了,并想知道一种可能的损坏数最小的损坏情况。

第一行输入两个正整数n,m,表示站点个数和直接连接数
后接m行,每行输入两个数u,v,表示u,v直接连接
第m + 2行输入一个正整数k,表示Tgopknight进行的测试次数
后接k行,每行输入两个数u,v,表示Tgopknight沙试u,v之间是否连通
Sample Input
5 4
2 1
5 3
3 1
4 3
2
2 4
3 2

第一行输出一个整数ans,表示最少损坏的站点数
后接一行ans个数,表示一种可能的损坏情况。
Sample Output
1
2

对于前30% 的数据,
$n,m \leq 15$
另有20% 的数据,保证网络是一条链
另有10% 的数据,$k \leq 3$
对于100%的数据,$3 \leq n,m \leq 10^5,0 \leq k \leq 3 \times 10^5$
本题有special judge
数据有梯度

------ 本文结束 ------