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
|
vector<vector<int>> adj;
vector<int> sz, in, out, nxt, par;
int t;
void dfs_sz(int v = 0, int from = -1) {
sz[v] = 1;
for (auto& u : adj[v]) {
if (u != from) {
dfs_sz(u, v);
sz[v] += sz[u];
}
if (adj[v][0] == from || sz[u] > sz[adj[v][0]]) {
swap(u, adj[v][0]);
}}}
void dfs_hld(int v = 0, int from = -1) {
par[v] = from;
in[v] = t++;
for (int u : adj[v]) {
if (u == from) continue;
nxt[u] = (u == adj[v][0] ? nxt[v] : u);
dfs_hld(u, v);
}
out[v] = t;
}
void init() {
int n = sz(adj);
sz.assign(n, 0); in.assign(n, 0); out.assign(n, 0);
nxt.assign(n, 0); par.assign(n, -1);
t = 0;
dfs_sz(); dfs_hld();
}
vector<pair<int, int>> get_intervals(int u, int v) {
vector<pair<int, int>> res;
while (true) {
if (in[v] < in[u]) swap(u, v);
if (in[nxt[v]] <= in[u]) {
res.emplace_back(in[u], in[v] + 1);
return res;
}
res.emplace_back(in[nxt[v]], in[v] + 1);
v = par[nxt[v]];
}}
int get_lca(int u, int v) {
while (true) {
if (in[v] < in[u]) swap(u, v);
if (in[nxt[v]] <= in[u]) return in[u];
v = par[nxt[v]];
}}
|
