This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// Tarjan's off-line LCA algorithm
// 依存ライブラリ
// ・グラフ辺構造体 (graph_000_basic.cpp)
struct OfflineLCA {
Graph<> G;
vector<int> node, anc, color, answers;
vector< vector< pair<int, int> > > queries;
int find(int k) { return node[k] < 0 ? k : find(node[k]); }
int size(int k) { return -node[find(k)]; }
void unite(int u, int v) {
u = find(u), v = find(v);
if(u == v) return;
if(size(u) < size(v)) swap(u, v);
node[u] += node[v];
node[v] = u;
}
void build(int cur, int par=-1) {
anc[cur] = cur;
for(auto e : G[cur]) {
if(e.to == par) continue;
build(e.to, cur);
unite(e.to, cur);
anc[find(cur)] = cur;
}
color[cur] = 1;
for(auto q : queries[cur]) {
int to, idx; tie(to, idx) = q;
if(color[to] == 1) {
int lca = anc[find(to)];
answers[idx] = lca;
}
}
}
OfflineLCA(Graph<> G, vector< pair<int, int> > Q, int root=0) : G(G) {
size_t N = G.size(), M = Q.size();
node = anc = color = vector<int>(N);
fill(node.begin(), node.end(), -1);
queries.resize(N); answers.resize(M);
for(size_t i=0; i<M; i++) {
int u, v; tie(u, v) = Q[i];
queries[u].emplace_back(v, i);
queries[v].emplace_back(u, i);
}
build(root);
}
int& operator[] (int k) { return answers[k]; }
};
#line 1 "graph/graph_023_offline_lca.cpp"
// Tarjan's off-line LCA algorithm
// 依存ライブラリ
// ・グラフ辺構造体 (graph_000_basic.cpp)
struct OfflineLCA {
Graph<> G;
vector<int> node, anc, color, answers;
vector< vector< pair<int, int> > > queries;
int find(int k) { return node[k] < 0 ? k : find(node[k]); }
int size(int k) { return -node[find(k)]; }
void unite(int u, int v) {
u = find(u), v = find(v);
if(u == v) return;
if(size(u) < size(v)) swap(u, v);
node[u] += node[v];
node[v] = u;
}
void build(int cur, int par=-1) {
anc[cur] = cur;
for(auto e : G[cur]) {
if(e.to == par) continue;
build(e.to, cur);
unite(e.to, cur);
anc[find(cur)] = cur;
}
color[cur] = 1;
for(auto q : queries[cur]) {
int to, idx; tie(to, idx) = q;
if(color[to] == 1) {
int lca = anc[find(to)];
answers[idx] = lca;
}
}
}
OfflineLCA(Graph<> G, vector< pair<int, int> > Q, int root=0) : G(G) {
size_t N = G.size(), M = Q.size();
node = anc = color = vector<int>(N);
fill(node.begin(), node.end(), -1);
queries.resize(N); answers.resize(M);
for(size_t i=0; i<M; i++) {
int u, v; tie(u, v) = Q[i];
queries[u].emplace_back(v, i);
queries[v].emplace_back(u, i);
}
build(root);
}
int& operator[] (int k) { return answers[k]; }
};