Bonus Project

Prerequisites: Breadth First Search / Depth First Search

Explanation: At first lets see two observation $-$

1. Company structure is a tree structure. The head of the company (employee number $1$) is the root of the tree.

2. For each query you don’t have to print answer online. So after final query, one bfs or dfs call is enough for getting final account balance for all employees.

So for each query sums up the amount $Y$ in node $X$ (team leader) and also sums up the amount $Y$ in initial account of node $X$ (as $X$ will get $2Y$ bonus).

Finally run a bfs or dfs from Node $1$ (head of the company). Using push down method to update each child account balance. Then calculate final account balance for each node $X$ by adding the initial balance with it.

One can also solve it using tree flattening and segment tree.

Time Complexity: for bfs or dfs,$$$O(n)$

Solution:
Setter’s Solution