Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct LCA {
- typedef vector<vector<int>> Graph;
- Graph G;
- vector<int> depth;
- vector<vector<int>> parent;
- int n, root, MAXLOG;
- LCA(int _n) {
- root = 0;
- n = _n;
- MAXLOG = (int)log2(_n) + 1;
- G.assign(_n, vector<int>());
- depth.assign(_n, 0);
- parent.assign(MAXLOG + 1, vector<int>(_n, 0));
- }
- void dfs(int v, int p, int d) {
- parent[0][v] = p;
- depth[v] = d;
- for(auto&& dst : G[v]) {
- if(dst != p) dfs(dst, v, d + 1);
- }
- }
- void init(int root = 0) {
- dfs(root, -1, 0);
- for(int k = 0; k + 1 < MAXLOG; k++) {
- for(int v = 0; v < n; v++) {
- if(parent[k][v] < 0) parent[k + 1][v] = -1;
- else parent[k + 1][v] = parent[k][parent[k][v]];
- }
- }
- }
- int lca(int u, int v) {
- if(depth[u] > depth[v]) swap(u, v);
- for(int k = 0; k < MAXLOG; k++) {
- if((depth[v] - depth[u]) >> k & 1) v = parent[k][v];
- }
- if(u == v) return u;
- for(int k = MAXLOG - 1; k >= 0; k--) {
- if(parent[k][u] != parent[k][v]) {
- u = parent[k][u];
- v = parent[k][v];
- }
- }
- return parent[0][u];
- }
- void add_edge(int a, int b) {
- G[a].emplace_back(b);
- G[b].emplace_back(a);
- }
- void print(int a, int b) {
- OUT(depth[a] + depth[b] - 2 * depth[lca(a, b)] + 1);
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement