Harshikaa and the Rain solution codechef- 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:

Harshikaa and the Rain solution codechef

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 MM-th 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 space-separated integers NN and MM – the number of nodes on the tree and the number of shake events.
  • N1N−1 lines follow, each line containing two space-separated integers UU and VV denoting an edge between node UU and VV on the tree.
  • The next line contains MM space-separated 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 MM-th shake.

Constraints

  • 1T10001≤T≤1000
  • 2N1000002≤N≤100000
  • 1U,VN1≤U,V≤N
  • UVU≠V
  • 1M1000001≤M≤100000
  • 1Ai1091≤Ai≤109
  • AA is strictly increasing
  • Sum of NN over all test cases is not more than 51055⋅105
  • Sum of MM over all test cases is not more than 41054⋅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 ii-th node.

    • At second 00R=[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 22R=[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 44RR 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 55R=[5,0,0,0,0]R=[5,0,0,0,0].

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

Leave a Comment

Your email address will not be published. Required fields are marked *