[toph.co] Value Assignment Problem 2

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Value Assignment Problem 2
Source            : toph.co
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 = 19;
 
vector <int> graph[maxn];
int depth[maxn], 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 LCA(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];
}
 
inline int dist(int u, int v)
{
      int lca = LCA(u, v);
      return depth[u] + depth[v] - 2*depth[lca];
}
 
int chainNo,
    chainHead[maxn],
    chainInd[maxn],
    chainPos[maxn],
    baseArray[maxn],
    posBase[maxn],
    ptr;
 
inline void hld(int u = 1, int p = -1)
{
      if (chainHead[chainNo] == -1) chainHead[chainNo] = u;
      chainInd[u] = chainNo;
      ptr++;
      baseArray[ptr] = 0;
      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 || v == bigChild) continue;
            chainNo++;
            hld(v, u);
      }
}
 
struct information
{
      bool lazy;
      int s;     // starting node of the tree
      int p;     // starting index of the array
      int k;     // distance of node (u, v) in the tree
      information(bool lazy = 0, int s = 0, int p = 0, int k = 0) :
            lazy(lazy), s(s), p(p), k(k) {}
} tree[maxn << 2];
 
struct tupple
{
      int s, p, k;
      tupple(int s = 0, int p = 0, int k = 0) :
            s(s), p(p), k(k) {}
};
 
inline void updateLazy(int node, tupple tpl)
{
      tree[node].lazy = 1;
      tree[node].s = tpl.s;
      tree[node].p = tpl.p;
      tree[node].k = tpl.k;
}
 
inline void updateNode(int node)
{
      int lft = node << 1;
      int rgt = lft | 1;
      tree[lft].lazy = tree[rgt].lazy = 1;
 
      tree[lft].s = tree[node].s;
      tree[lft].p = tree[node].p;
      tree[lft].k = tree[node].k;
 
      tree[rgt].s = tree[node].s;
      tree[rgt].p = tree[node].p;
      tree[rgt].k = tree[node].k;
 
      tree[node].lazy = 0;
}
 
inline void rangeUpdate(int node, int a, int b, int i, int j, tupple tpl)
{
      if (a == i && b == j)
      {
            updateLazy(node, tpl);
            return;
      }
      if (tree[node].lazy == 1)
      {
            updateNode(node);
      }
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      if (j <= mid)
      {
            rangeUpdate(lft, a, mid, i, j, tpl);
      }
      else if (i > mid)
      {
            rangeUpdate(rgt, mid+1, b, i, j, tpl);
      }
      else
      {
            rangeUpdate(lft, a, mid, i, mid, tpl);
            rangeUpdate(rgt, mid+1, b, mid+1, j, tpl);
      }
}
 
inline tupple pointQuery(int node, int a, int b, int pos)
{
      if (a == pos && b == pos)
      {
            tupple tpl;
            tpl.s = tree[node].s;
            tpl.p = tree[node].p;
            tpl.k = tree[node].k;
            return tpl;
      }
      if (tree[node].lazy == 1)
      {
            updateNode(node);
      }
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = (a + b) >> 1;
      if (pos <= mid) return pointQuery(lft, a, mid, pos);
      else return pointQuery(rgt, mid+1, b, pos);
}
 
inline void updatePath(int u, int v, tupple tpl)
{
      // u - always lowest node
      // v - lca
      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;
                  rangeUpdate(1, 1, N, l, r, tpl);
                  break;
            }
            int l = posBase[ chainHead[uChain] ];
            int r = posBase[u];
            assert(l <= r);
            rangeUpdate(1, 1, N, l, r, tpl);
            u = father[ chainHead[uChain] ][0];
      }
}
 
inline void update_hld(int u, int v, int p)
{
      int lca = LCA(u, v);
      int dst = depth[u] + depth[v] - 2*depth[lca];
 
      tupple tpl;
      tpl.s = u;
      tpl.p = p;
      tpl.k = dst;
 
      updatePath(u, lca, tpl);
      updatePath(v, lca, tpl);
}
 
inline void init()
{
      ptr = 0;
      chainNo = 0;
      for (int i = 0; i < maxn; i++)
      {
            graph[i].clear();
            subtreeSize[i] = 0;
            chainHead[i] = -1;
            chainInd[i] = 0;
            depth[i] = 0;
            baseArray[i] = 0;
            posBase[i] = 0;
            for (int j = 0; j < logn; j++) father[i][j] = 0;
      }
}
 
inline int read()
{
      int a;
      scanf("%d", &a);
      return a;
}
 
int arr[maxn];
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      init();
 
      int tnode = read();
      int arr_sz = read();
      for (int e = 1; e < tnode; e++)
      {
            int u = read();
            int v = read();
            graph[u].emplace_back(v);
            graph[v].emplace_back(u);
      }
      for (int i = 1; i <= arr_sz; i++)
      {
            arr[i] = read();
      }
      depth[1] = 1;
      dfs();
      hld();
      N = ptr;
 
      int tquery = read();
 
      while (tquery--)
      {
            int type = read();
            if (type == 1)
            {
                  int u = read();
                  int v = read();
                  int p = read();
                  update_hld(u, v, p);
            }
            else
            {
                  int u = read();
                  int pos = posBase[u];
                  tupple tpl = pointQuery(1, 1, N, pos);
 
                  int s = tpl.s;
                  int p = tpl.p;
                  int k = tpl.k;
 
                  if (s == 0)
                  {
                        puts("0");
                        continue;
                  }
                  int original_index = dist(s, u) + p;
                  int ans = arr[original_index];
                  printf("%d\n", ans);
            }
      }
}