-
Notifications
You must be signed in to change notification settings - Fork 30
/
OfflineLCA.ts
112 lines (102 loc) · 2.35 KB
/
OfflineLCA.ts
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
// https://ei1333.github.io/library/graph/tree/offline-lca.hpp
// O(n*α(n)),LCA离线,一般用于树上莫队
/**
* 离线求LCA.
*/
function offLineLca(
tree: number[][],
queries: [start: number, end: number][] | number[][],
root = 0
): number[] {
const n = tree.length
const data = new Int32Array(n)
const stack = new Uint32Array(n)
const mark = new Int32Array(n)
const ptr = new Uint32Array(n)
const res = Array(queries.length)
for (let i = 0; i < queries.length; ++i) res[i] = -1
let top = 0
stack[top] = root
const q: [next: number, ei: number][][] = Array(n)
for (let i = 0; i < n; ++i) {
q[i] = []
mark[i] = -1
data[i] = -1
ptr[i] = tree[i].length
}
queries.forEach(([start, end], i) => {
q[start].push([end, i])
q[end].push([start, i])
})
while (top !== -1) {
const u = stack[top]
const nexts = tree[u]
if (mark[u] === -1) {
mark[u] = u
} else {
union(u, nexts[ptr[u]])
mark[find(u)] = u
}
if (!run(u)) {
q[u].forEach(([v, i]) => {
if (mark[v] !== -1 && res[i] === -1) {
res[i] = mark[find(v)]
}
})
--top
}
}
return res
function union(key1: number, key2: number): boolean {
let root1 = find(key1)
let root2 = find(key2)
if (root1 === root2) return false
if (data[root1] > data[root2]) {
root1 ^= root2
root2 ^= root1
root1 ^= root2
}
data[root1] += data[root2]
data[root2] = root1
return true
}
function find(key: number): number {
if (data[key] < 0) return key
data[key] = find(data[key])
return data[key]
}
function run(u: number): boolean {
const nexts = tree[u]
while (ptr[u]) {
const v = nexts[--ptr[u]]
if (mark[v] === -1) {
stack[++top] = v
return true
}
}
return false
}
}
export { offLineLca }
if (require.main === module) {
const n = 5
const edges = [
[0, 1],
[0, 2],
[0, 3],
[2, 4]
]
const tree: number[][] = Array(n)
for (let i = 0; i < n; ++i) tree[i] = []
edges.forEach(([u, v]) => {
tree[u].push(v)
tree[v].push(u)
})
const queries = [
[1, 3],
[2, 4],
[0, 4]
]
const res = offLineLca(tree, queries)
console.log(res)
}