Advertisement
Guest User

Untitled

a guest
Mar 27th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.45 KB | None | 0 0
  1. struct LCA {
  2. typedef vector<vector<int>> Graph;
  3. Graph G;
  4. vector<int> depth;
  5. vector<vector<int>> parent;
  6. int n, root, MAXLOG;
  7.  
  8. LCA(int _n) {
  9. root = 0;
  10. n = _n;
  11. MAXLOG = (int)log2(_n) + 1;
  12. G.assign(_n, vector<int>());
  13. depth.assign(_n, 0);
  14. parent.assign(MAXLOG + 1, vector<int>(_n, 0));
  15. }
  16.  
  17. void dfs(int v, int p, int d) {
  18. parent[0][v] = p;
  19. depth[v] = d;
  20. for(auto&& dst : G[v]) {
  21. if(dst != p) dfs(dst, v, d + 1);
  22. }
  23. }
  24.  
  25. void init(int root = 0) {
  26. dfs(root, -1, 0);
  27. for(int k = 0; k + 1 < MAXLOG; k++) {
  28. for(int v = 0; v < n; v++) {
  29. if(parent[k][v] < 0) parent[k + 1][v] = -1;
  30. else parent[k + 1][v] = parent[k][parent[k][v]];
  31. }
  32. }
  33. }
  34.  
  35. int lca(int u, int v) {
  36. if(depth[u] > depth[v]) swap(u, v);
  37. for(int k = 0; k < MAXLOG; k++) {
  38. if((depth[v] - depth[u]) >> k & 1) v = parent[k][v];
  39. }
  40. if(u == v) return u;
  41. for(int k = MAXLOG - 1; k >= 0; k--) {
  42. if(parent[k][u] != parent[k][v]) {
  43. u = parent[k][u];
  44. v = parent[k][v];
  45. }
  46. }
  47. return parent[0][u];
  48. }
  49.  
  50. void add_edge(int a, int b) {
  51. G[a].emplace_back(b);
  52. G[b].emplace_back(a);
  53. }
  54.  
  55. void print(int a, int b) {
  56. OUT(depth[a] + depth[b] - 2 * depth[lca(a, b)] + 1);
  57. }
  58. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement