daily pastebin goal
32%
SHARE
TWEET

Untitled

a guest Jan 12th, 2018 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // to run:
  2. // dfsSZ(0, -1, 0);
  3. // dfsHLD(0, -1, 0);
  4. //
  5. // [tin[x], tout[x]] --- subtree of x
  6. // [tin[TO[x]], tin[x]] --- path from TO[x] to x
  7.  
  8. VI g[MAX];     // graph
  9. int SZ[MAX];   // size of the subtree
  10. int H[MAX];    // height of the vertex
  11. int P[MAX];    // parent of the vertex
  12. int TO[MAX];   // top node of the heavy path
  13. int tin[MAX];
  14. int tout[MAX];
  15. int timer = 0;
  16.  
  17. void dfsSZ(int x, int p, int h)
  18. {
  19.     SZ[x] = 1;
  20.     H[x] = h;
  21.     P[x] = p;
  22.     FOR (i, 0, SZ(g[x]))
  23.     {
  24.         int to = g[x][i];
  25.         if (to == p) continue;
  26.  
  27.         dfsSZ(to, x, h + 1);
  28.         SZ[x] += SZ[to];
  29.         if (g[x][0] == p || SZ[to] > SZ[g[x][0]])
  30.         {
  31.             swap(g[x][0], g[x][i]);
  32.         }
  33.     }
  34. }
  35.  
  36. void dfsHLD(int x, int p, int v)
  37. {
  38.     tin[x] = timer++;
  39.     TO[x] = v;
  40.     FOR (i, 0, SZ(g[x]))
  41.     {
  42.         int to = g[x][i];
  43.         if (to == p) continue;
  44.         if (i == 0) dfsHLD(to, x, v);
  45.         else dfsHLD(to, x, to);
  46.     }
  47.     tout[x] = timer - 1;
  48. }
  49.  
  50. int get(int x, int y) // query on path x-y
  51. {
  52.     int res = 0;
  53.     while(true)
  54.     {
  55.         int tx = TO[x];
  56.         int ty = TO[y];
  57.         if (tx == ty) // same heavy path
  58.         {
  59.             int t1 = tin[x];
  60.             int t2 = tin[y];
  61.             if (t1 > t2) swap(t1, t2);
  62.             if (t1 < t2)
  63.             {
  64.                 res = max(res, R.get(t1 + 1, t2)); // lca not considered
  65.             }
  66.             break;
  67.         }
  68.  
  69.         if (H[tx] < H[ty])
  70.         {
  71.             swap(tx, ty);
  72.             swap(x, y);
  73.         }
  74.  
  75.         res = max(res, R.get(tin[tx], tin[x]));
  76.         x = P[tx];
  77.     }
  78.     return res;
  79. }
RAW Paste Data
Top