[UVa] 13164 - Performance Review

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13164 - Performance Review
Source            : UVa Online Judge
Category          : Graph Theory, Data Structure
Algorithm         : DSU on Tree, Binary Indexed Tree
Verdict           : Accepted 

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll              long long
 
static const int maxn = 2e5 + 5;
 
ll tree[maxn];
int N; // N = max rank
 
vector <int> graph[maxn];
int rnk[maxn], tim[maxn];
int subtreeSize[maxn];
ll ans[maxn];
bool big[maxn];
 
inline void update(int pos, int val)
{
      while (pos <= N)
      {
            tree[pos] += val;
            pos += pos & (-pos);
      }
}
 
inline ll read(int pos)
{
      ll sum = 0;
      while (pos > 0)
      {
            sum += tree[pos];
            pos -= pos & (-pos);
      }
      return sum;
}
 
inline void dfs(int u, int p = -1)
{
      subtreeSize[u] = 1;
      for (int v : graph[u])
      {
            if (v == p) continue;
            dfs(v, u);
            subtreeSize[u] += subtreeSize[v];
      }
}
 
inline void add(int u, int p)
{
      update(rnk[u], tim[u]);
      for (int v : graph[u])
      {
            if (v == p || big[v]) continue;
            add(v, u);
      }
}
 
inline void remov(int u, int p)
{
      update(rnk[u], -tim[u]);
      for (int v : graph[u])
      {
            if (v == p || big[v]) continue;
            remov(v, u);
      }
}
 
inline ll getTime(int u)
{
      return read(rnk[u] - 1);
}
 
inline void dsu(int u, int p, bool keep)
{
      int mx = -1;
      int bigChild = -1;
      for (int v : graph[u])
      {
            if (v == p) continue;
            if (subtreeSize[v] > mx) mx = subtreeSize[v], bigChild = v;
      }
      for (int v : graph[u])
      {
            if (v == p || v == bigChild) continue;
            dsu(v, u, 0);
      }
      if (bigChild != -1) dsu(bigChild, u, 1), big[bigChild] = 1;
      add(u, p);
      ans[u] = getTime(u);
      if (bigChild != -1) big[bigChild] = 0;
      if (keep == 0) remov(u, p);
}
 
inline void clean()
{
      for (int i = 0; i < maxn; i++)
      {
            graph[i].clear();
            rnk[i] = 0;
            tim[i] = 0;
            tree[i] = 0;
            big[i] = 0;
            subtreeSize[i] = 0;
            ans[i] = 0;
      }
}
 
int main()
{
      int tnode;
      while (cin >> tnode)
      {
            int m, r, t;
            int root = -1;
            N = 0;
            for (int i = 1; i <= tnode; i++)
            {
                  cin >> m >> r >> t;
                  rnk[i] = r;
                  tim[i] = t;
                  if (r > N) N = r;
                  if (m == -1) root = i;
                  if (m != -1)
                  {
                        graph[i].push_back(m);
                        graph[m].push_back(i);
                  }
            }
            dfs(root, -1);
            dsu(root, -1, 0);
            for (int i = 1; i <= tnode; i++) cout << ans[i] << endl;
            clean();
      }
}