Harshikaa and the Rain solution codechef

For Solution
Click Here!
There is a tree with NN nodes numbered from 11 to NN outside Harshikaa’s house. The tree is rooted at node 11. Initially the tree was dry, there were no raindrops on any node of the tree. Suddenly it started raining, and every second a drop falls on all the leaf nodes of the tree. Also, every second any drop which wasn’t already on the root node moves one node closer to the root.
Sometimes, strong winds shake the tree and all drops which were not on the root fall off. It is known that the wind will shake the tree MM times at A1,A2,…AMA1,A2,…AM seconds after it started raining.
If multiple events happen at the same second, they are in this order:
 Raindrops move one node closer to the root.
 New raindrops fall on the leaves.
 Wind shakes the tree.
How many drops are there at the root right after the MMth shake?
Input Format Harshikaa and the Rain solution codechef
 The first line of each input contains TT – the number of test cases. The test cases then follow.
 The first line of each test case contains two spaceseparated integers NN and MM – the number of nodes on the tree and the number of shake events.
 N−1N−1 lines follow, each line containing two spaceseparated integers UU and VV denoting an edge between node UU and VV on the tree.
 The next line contains MM spaceseparated integers A1,A2,…,AMA1,A2,…,AM – the timestamp of the shakes.
Output Format Harshikaa and the Rain solution codechef
For each test case, output in a single line the number of raindrops on the root right after the MMth shake.
Constraints
 1≤T≤10001≤T≤1000
 2≤N≤1000002≤N≤100000
 1≤U,V≤N1≤U,V≤N
 U≠VU≠V
 1≤M≤1000001≤M≤100000
 1≤Ai≤1091≤Ai≤109
 AA is strictly increasing
 Sum of NN over all test cases is not more than 5⋅1055⋅105
 Sum of MM over all test cases is not more than 4⋅1054⋅105
Harshikaa and the Rain solution codechef Sample Input 1
1
5 2
2 1
1 3
4 3
3 5
2 5
Sample Output 1
5
Explanation Harshikaa and the Rain solution codechef

Test case 11: Let’s define an array RR, where RiRi is the number of raindrops on the iith node.

At second 00, R=[0,0,0,0,0]R=[0,0,0,0,0].

At second 11, a raindrop fell on all leaves. RR becomes [0,1,0,1,1][0,1,0,1,1].

At second 22,
 Firstly, raindrops moved closer to the root, so RR becomes [1,0,2,0,0][1,0,2,0,0].
 Secondly, a raindrop fell on all leaves, so RR becomes [1,1,2,1,1][1,1,2,1,1].
 Thirdly, the tree was shook, so every raindrop except the one on root fell. At the end of second 22, R=[1,0,0,0,0]R=[1,0,0,0,0].

At second 33, new raindrops fell, and RR becomes [1,1,0,1,1][1,1,0,1,1].

At second 44, RR becomes [2,1,2,1,1][2,1,2,1,1].

At second 55,
 Firstly, raindrops moved closer to the root, so RR becomes [5,0,2,0,0][5,0,2,0,0].
 Secondly, a raindrop fell on all leaves, so RR becomes [5,1,2,1,1][5,1,2,1,1].
 Thirdly, the tree was shook, so every raindrop except the one on root fell. At the end of second 55, R=[5,0,0,0,0]R=[5,0,0,0,0].

Therefore, at the end there were 55 drops at the root.

For Solution
Click Here!