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<snippet>
<content><![CDATA[
int n, l;
vector<vector<int>> adj; //upd adj
int _q = 0; //update it to _q if wt ed tree is used
vector<vector<pair<int, int>>> wadj;
vector<int> wt;
int timer;
vector<int> tin, tout, depth;
vector<vector<int>> up;
void dfs(int v, int p, int dep) //depth is extra,in case needed...
{
tin[v] = ++timer;
up[v][0] = p;
depth[v] = dep;
for (int i = 1; i <= l; ++i)
up[v][i] = up[up[v][i - 1]][i - 1];
for (int u : adj[v]) {
if (u != p)
dfs(u, v, dep + 1);
}
tout[v] = ++timer;
}
void wdfs(int v, int p, int sofar)
{
wt[v] = sofar;
for (auto &[u, w] : wadj[v]) {
if (u != p)
wdfs(u, v, sofar + w);
}
}
bool is_ancestor(int u, int v)
{
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v)
{
if (is_ancestor(u, v))
return u;
if (is_ancestor(v, u))
return v;
for (int i = l; i >= 0; --i) {
if (!is_ancestor(up[u][i], v))
u = up[u][i];
}
return up[u][0];
}
int distance(int u, int v) {
int anc = lca(u, v);
return abs(depth[u] - depth[anc]) + abs(depth[anc] - depth[v]);
}
int weight(int u, int v) {
int anc = lca(u, v);
return abs(wt[u] - wt[anc]) + abs(wt[anc] - wt[v]);
}
void preprocess(int root) {
n = adj.size();
tin.resize(n);
tout.resize(n);
depth.resize(n);
timer = 0;
l = ceil(log2(n));
up.assign(n, vector<int>(l + 1));
dfs(root, root, 0);
if(_q){
wt.resize(n);
wdfs(root,root,0);
}
}
//later :: may change lca template into lambda as jiangly template below for easy modification in code.
// https://codeforces.com/contest/1878/submission/225330664
]]></content>
<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
<tabTrigger>lca</tabTrigger>
<!-- Optional: Set a scope to limit where the snippet will trigger -->
<scope>source.c++</scope>
</snippet>