[Gym] Subway Lines

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Subway Lines
Source            : Gym
Category          : Data Structure, Graph Theory, Tree
Algorithm         : Heavy Light Decomposition, Segment Tree, Lazy Propagation
Verdict           : Accepted



#include "bits/stdc++.h"  
   
using namespace std;  
   
static const int maxn = 1e5 + 5;  
static const int logn = 18;  
   
vector <int> graph[maxn];  
int depth[maxn];  
int father[maxn][logn];  
int subtreeSize[maxn];  
   
int N;  
   
inline void dfs(int u = 1, int p = -1)  
{  
      for (int i = 1; i < logn; i++)  
      {  
            father[u][i] = father[ father[u][i-1] ][i-1];  
      }  
      subtreeSize[u] = 1;  
      for (int v : graph[u])  
      {  
            if (v == p) continue;  
            depth[v] = depth[u] + 1;  
            father[v][0] = u;  
            dfs(v, u);  
            subtreeSize[u] += subtreeSize[v];  
      }  
}  
   
inline int findLCA(int u, int v)  
{  
      if (depth[u] < depth[v]) swap(u, v);  
      for (int i = logn-1; i >= 0; i--)  
      {  
            if (depth[ father[u][i] ] >= depth[v])  
            {  
                  u = father[u][i];  
            }  
      }  
      if (u == v) return u;  
      for (int i = logn-1; i >= 0; i--)  
      {  
            if (father[u][i] != father[v][i])  
            {  
                  u = father[u][i];  
                  v = father[v][i];  
            }  
      }  
      return father[v][0];  
}  
   
   
int chainNo,  
    chainHead[maxn],  
    chainInd[maxn],  
    chainPos[maxn],  
    baseArray[maxn],  
    posBase[maxn],  
    ptr;  
   
struct segmentTree  
{  
      int sum, lazy;  
      segmentTree(int sum = 0, int lazy = -1) :  
            sum(sum), lazy(lazy) {}  
} Tree[maxn << 2];  
   
inline void updateLazy(int node, int a, int b, int val)  
{  
      Tree[node].sum = (b - a + 1) * val;  
      Tree[node].lazy = val;  
}  
   
inline void updateNode(int node, int a, int b)  
{  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      Tree[lft].sum = (mid - a + 1) * Tree[node].lazy;  
      Tree[rgt].sum = (b - mid) * Tree[node].lazy;  
      Tree[lft].lazy = Tree[rgt].lazy = Tree[node].lazy;  
   
      Tree[node].lazy = -1;  
}  
   
inline void update(int node, int a, int b, int i, int j, int val)  
{  
      if (a == i && b == j)  
      {  
            updateLazy(node, a, b, val);  
            return;  
      }  
      if (Tree[node].lazy != -1)  
      {  
            updateNode(node, a, b);  
      }  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      if (j <= mid)  
      {  
            update(lft, a, mid, i, j, val);  
      }  
      else if (i > mid)  
      {  
            update(rgt, mid+1, b, i, j, val);  
      }  
      else  
      {  
            update(lft, a, mid, i, mid, val);  
            update(rgt, mid+1, b, mid+1, j, val);  
      }  
      Tree[node].sum = Tree[lft].sum + Tree[rgt].sum;  
}  
   
inline int query(int node, int a, int b, int i, int j)  
{  
      if (a == i && b == j) return Tree[node].sum;  
      if (Tree[node].lazy != -1)  
      {  
            updateNode(node, a, b);  
      }  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      int sum = 0;  
      if (j <= mid)  
      {  
            sum += query(lft, a, mid, i, j);  
      }  
      else if (i > mid)  
      {  
            sum += query(rgt, mid+1, b, i, j);  
      }  
      else  
      {  
            sum += query(lft, a, mid, i, mid);  
            sum += query(rgt, mid+1, b, mid+1, j);  
      }  
      Tree[node].sum = Tree[lft].sum + Tree[rgt].sum;  
      return sum;  
}  
   
inline void hld(int u = 1, int p = -1)  
{  
      if (chainHead[chainNo] == -1) chainHead[chainNo] = u;  
      chainInd[u] = chainNo;  
      ptr++;  
      baseArray[ptr] = u;  
      posBase[u] = ptr;  
      int mx = -1, bigChild = -1;  
      for (int v : graph[u])  
      {  
            if (v == p) continue;  
            if (subtreeSize[v] > mx) mx = subtreeSize[v], bigChild = v;  
      }  
      if (bigChild != -1) hld(bigChild, u);  
      for (int v : graph[u])  
      {  
            if (v == p or bigChild == v) continue;  
            chainNo++;  
            hld(v, u);  
      }  
}  
   
inline void update_path(int u, int v)  
{  
      int uChain, vChain = chainInd[v];  
      while (true)  
      {  
            uChain = chainInd[u];  
            if (uChain == vChain)  
            {  
                  int l = posBase[v];  
                  int r = posBase[u];  
                  if (l > r) break;  
                  update(1, 1, N, l, r, 1);  
                  break;  
            }  
            int l = posBase[ chainHead[uChain] ];  
            int r = posBase[u];  
            assert(l <= r);  
            update(1, 1, N, l, r, 1);  
            u = father[ chainHead[uChain] ][0];  
      }  
}  
   
inline void update_lca(int u, int v)  
{  
      int lca = findLCA(u, v);  
      update_path(u, lca);  
      update_path(v, lca);  
}  
   
inline int query_path(int u, int v)  
{  
      int uChain;  
      int vChain = chainInd[v];  
      int sum = 0;  
      while (true)  
      {  
            uChain = chainInd[u];  
            if (uChain == vChain)  
            {  
                  int l = posBase[v];  
                  int r = posBase[u];  
                  if (l > r) break;  
                  sum += query(1, 1, N, l, r);  
                  break;  
            }  
            int l = posBase[ chainHead[uChain] ];  
            int r = posBase[u];  
            assert(l <= r);  
            sum += query(1, 1, N, l, r);  
            u = father[ chainHead[uChain] ][0];  
      }  
      return sum;  
}  
   
inline int query_lca(int u, int v)  
{  
      int lca = findLCA(u, v);  
      int sum1 = query_path(u, lca);  
      int sum2 = query_path(v, lca);  
      int sumlca = query_path(lca, lca);  
      int sum = sum1 + sum2 - sumlca;  
      return sum;  
}  
   
inline void init()  
{  
      ptr = 0;  
      chainNo = 0;  
      for (int i = 0; i < maxn; i++)  
      {  
            graph[i].clear();  
            subtreeSize[i] = 0;  
            depth[i] = 0;  
            baseArray[i] = 0;  
            posBase[i] = 0;  
            chainInd[i] = 0;  
            chainHead[i] = -1;  
            for (int j = 0; j < logn; j++) father[i][j] = 0;  
      }  
}  
   
int main()  
{  
      freopen("in.txt", "r", stdin);  
   
      init();  
      int tnode, tquery;  
      scanf("%d %d", &tnode, &tquery);  
      for (int i = 1; i < tnode; i++)  
      {  
            int u, v;  
            scanf("%d %d", &u, &v);  
            graph[u].emplace_back(v);  
            graph[v].emplace_back(u);  
      }  
      N = tnode;  
      depth[1] = 1;  
      dfs();  
      hld();  
      while (tquery--)  
      {  
            int a, b, c, d;  
            scanf("%d %d %d %d", &a, &b, &c, &d);  
            update(1, 1, N, 1, N, 0);  
            update_lca(a, b);  
            int ans = query_lca(c, d);  
            printf("%d\n", ans);  
      }  
}