[Codeforces] E. On Changing Tree

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. On Changing Tree
Source            : Codeforces
Category          : Data Structure, Graph Theory, Tree
Algorithm         : Heavy Light Decomposition, Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll           long long int  
  
static const int maxn = 3e5 + 5;  
static const int logn = 21;  
static const ll mod = 1e9 + 7;  
  
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];  
      }  
}  
  
int chainHead[maxn];  
int chainNo;  
int chainInd[maxn];  
int ptr;  
int posBase[maxn];  
  
inline void hld(int u = 1, int p = -1)  
{  
      if (chainHead[ chainNo ] == -1) chainHead[ chainNo ] = u;  
      ptr++;  
      posBase[u] = ptr;  
      chainInd[u] = chainNo;  
      int mx = -1;  
      int 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 v == bigChild) continue;  
            chainNo++;  
            hld(v, u);  
      }  
}  
  
// value of a particular vertex:  
// All the value which are added in the ancestor of node v are also  
// added to node v. So, we can find added value by the sum of all  
// node from root to node v.  
// Now, to find the value of subtraction(i.e. k), we know,  
// if a k value added on u vertex, this affects on v vertex by following,  
//             distance(u, v) * k  
//            = (level[v] - level[u]) * k  
// we know, level[v] is constant. So, we can take level[v] as a common term  
// from all ancestor of v.  
// So, our final ans will be  
//           sum_add - (sum_k * level[v] - sum_u_k)  
// sum_add = all added value in the ancestor of v  
// sum_k = all k value added in the ancestor of v  
// sum_u_k = sum of level[u] * k, where u is ancestor of v  
  
struct segmentTree  
{  
      ll sumOne, sumTwo, sumThree;  
      segmentTree(ll sum1 = 0, ll sum2 = 0, ll sum3 = 0) : sumOne(sum1), sumTwo(sum2), sumThree(sum3) {}  
      inline void assignLeaf(ll sum1, ll sum2, ll sum3)  
      {  
            sumOne = sum1;  
            sumTwo = sum2;  
            sumThree = sum3;  
      }  
      inline void marge(segmentTree &lft, segmentTree &rgt)  
      {  
            sumOne = (lft.sumOne + rgt.sumOne) % mod;  
            sumTwo = (lft.sumTwo + rgt.sumTwo) % mod;  
            sumThree = (lft.sumThree + rgt.sumThree) % mod;  
      }  
} Tree[maxn << 2];  
  
inline void update(int node, int a, int b, int pos, segmentTree tpl)  
{  
      if (a == pos && b == pos)  
      {  
            Tree[node].marge(Tree[node], tpl);  
            return;  
      }  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      if (pos <= mid)  
      {  
            update(lft, a, mid, pos, tpl);  
      }  
      else if (pos > mid)  
      {  
            update(rgt, mid+1, b, pos, tpl);  
      }  
      Tree[node].marge(Tree[lft], Tree[rgt]);  
}  
  
inline segmentTree query(int node, int a, int b, int i, int j)  
{  
      if (a > b or a > j or b < i) return segmentTree();  
      if (a >= i && b <= j) return Tree[node];  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      segmentTree p, q, res;  
      p = query(lft, a, mid, i, j);  
      q = query(rgt, mid+1, b, i, j);  
      res.marge(p, q);  
      return res;  
}  
  
inline void updateNode(int u, ll x, ll k)  
{  
      int level = depth[u];  
      int pos = posBase[u];  
      ll mul = (k * (ll)level) % mod;  
      segmentTree tpl = segmentTree(x, k, mul);  
      update(1, 1, N, pos, tpl);  
}  
  
inline segmentTree query_path(int u, int v = 1)  
{  
      segmentTree res = segmentTree();  
      int uChain;  
      int vChain = chainInd[v];  
      while (true)  
      {  
            uChain = chainInd[u];  
            if (uChain == vChain)  
            {  
                  int l = posBase[v];  
                  int r = posBase[u];  
                  assert(l <= r);  
                  segmentTree q = query(1, 1, N, l, r);  
                  res.marge(res, q);  
                  break;  
            }  
            int l = posBase[ chainHead[uChain] ];  
            int r = posBase[u];  
            assert(l <= r);  
            segmentTree q = query(1, 1, N, l, r);  
            res.marge(res, q);  
            u = father[ chainHead[uChain] ][0];  
      }  
      return res;  
}  
  
inline ll query_ans(int u)  
{  
      segmentTree res = query_path(u);  
      ll ans = (res.sumOne - (((res.sumTwo * depth[u]) % mod) - res.sumThree) + mod) % mod;  
      return ans;  
}  
  
inline void init()  
{  
      ptr = 0;  
      chainNo = 0;  
      for (int i = 0; i < maxn; i++)  
      {  
            graph[i].clear();  
            depth[i] = 0;  
            subtreeSize[i] = 0;  
            chainHead[i] = -1;  
            chainInd[i] = 0;  
            posBase[i] = 0;  
            for (int j = 0; j < logn; j++) father[i][j] = 0;  
      }  
}  
  
int main()  
{  
      //freopen("in.txt", "r", stdin);  
  
      init();  
  
      int tnode;  
      scanf("%d", &tnode);  
      for (int v = 2; v <= tnode; v++)  
      {  
            int u;  
            scanf("%d", &u);  
            graph[u].emplace_back(v);  
            graph[v].emplace_back(u);  
      }  
      N = tnode;  
      depth[1] = 1;  
      dfs();  
      hld();  
      int tquery;  
      scanf("%d", &tquery);  
      while (tquery--)  
      {  
            int type;  
            scanf("%d", &type);  
            if (type == 1)  
            {  
                  int u;  
                  ll x, k;  
                  scanf("%d %lld %lld", &u, &x, &k);  
                  updateNode(u, x, k);  
            }  
            else  
            {  
                  int v;  
                  scanf("%d", &v);  
                  ll ans = query_ans(v);  
                  printf("%lld\n", ans);  
            }  
      }  
}