Add and Compute Path
All submissions for this problem are available.
In the kingdom of Baratheons, there is a strict hierarchy in the army. The leader of the army is the king under whose command are a set of soldiers. Each soldier commands a certain section of army, that is there are certain soldiers under him who may be commanding some more soldiers, and the similar hierarchical structure is followed downwards, till the lowest rank of soldiers. Note that if soldier A commands soldier B and B commands C, then C also comes under the purview of A, however it will be said that B is under the direct command of A and C is under the direct command of B. Also note that each soldier has a unique hierarchical path to the king.
The army commission, a different body, may decide to give certain units of power to a particular section of the army. To do this, the commission gives K units of power to the soldier commanding a section, which is cloned and each soldier under his command, including himself, receives K units of power. Remember, initially all soldiers have zero units of power.
In times of war, a team of soldiers may be selected from across sections. The team is selected in the following way: given two soldiers A and B, all the soldiers in the path through the hierarchical structure from A to B, are included in the team. For such a team, you have to calculate the total power of the team.
First line contains three space separated integers N, K and R.
N represents the number of soldiers
R represents the id of the king.
Next N-1 lines describes the hierarchical structure. Each line consists of two integers A and B, signifying that soldier B is under the direct command of soldier A.
K following lines represent operations of the following types.
For a query operation, the first character is Q, followed by two space separated integers X and Y.
For an update operation, the first character is U, followed by two space separated integers S and T, such that the soldier S is given T units of power to be cloned and distributed to soldiers under his command.
For each query operation, output the total power of all soldiers in the path through the hierarchical structure from X to Y.
- 1 ≤ N ≤ 1e5
- 1 ≤ K ≤ 1e5
- 1 ≤ X,Y,S ≤ 1e5
- Absolute(T) ≤ 1000
5 3 1
U 3 5
Q 4 5
Q 4 1
Initially all soldiers have 0 power. When the update operation is executed, soldiers 3, 4 and 5 get 5 units of power.
For the first query, all soldiers in the path from 4 to 5 are added up, i.e, power(4) + power(3) + power(5) = 15, is given as output.
For second query, all soldiers in the path from 4 to 1 are added up, i.e., power(4) + power(3) + power(1) = 10, is given as output.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions