Farmers of Wasseypur solution codechef

Farmers of Wasseypur solution codechef

Not everything in Wasseypur is about gangs and guns. There are normal people too! Ashok is a simple farmer who has the misfortune of living in Wasseypur. He plants his seeds and works the land with his family like an honest man.

Through his hard work and grit he can turn his seeds into lush crops. However, not all seeds are equal – some seeds are good, some are bad. Seeds can be one of 44 types – {2,1,1,2}{−2,−1,1,2}. Ashok goes to the farmer’s market to buy some seeds where he meets Uday, an eccentric rich merchant. Ashok doesn’t have enough money to buy all the seeds he can plant. Taking pity on him, Uday proposes a strange game.

Farmers of Wasseypur solution codechef

Uday sets out NN seeds out in a pattern resembling a tree. Ashok can then choose one simple path in this tree and take every seed along this path. The path must not be empty, i.e, it should contain at least one vertex of the tree.

The total yield of the seeds Ashok receives equals the product of all their types. Given this tree and the type of seed placed at each vertex, what is the maximum yield Ashok can obtain?

Farmers of Wasseypur solution codechef

The answer can be large, so print it modulo 109+7109+7. If the answer is negative, print the positive remainder obtained on division by 109+7109+7 – that is, if the answer is 1−1, print 10000000061000000006.

Input Format

Farmers of Wasseypur solution codechef

  • The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN, denoting the number of seeds.
  • Each of the next N1N−1 lines contains two integers aa and bb, denoting that the aa-th and bb-th seeds are connected in tree.
  • The (N+1)(N+1)-th line of each test case consists of NN integers, S1,S2,S3,SNS1,S2,S3,…SNSiSi represents the type of the ithith seed.

Output Format

For each test case, print a single integer denoting the maximum yield that Ashok can get modulo 109+7109+7.

Constraints

Farmers of Wasseypur solution codechef

  • 1T100001≤T≤1 0000
  • 1N1051≤N≤105
  • Si{2,1,1,2}Si∈{−2,−1,1,2}
  • The sum of NN over all test cases does not exceed 21052⋅105.

Sample Input 1 

2
5
1 2
2 3
3 4
1 5
2 2 -1 -2 2
5
1 2
1 3
1 4
1 5
-1 -1 -1 -1 2

Sample Output 1

Farmers of Wasseypur solution codechef

16
2

Explanation

Test case 1:

One possible path giving the maximum product is {5,1,2,3,4}{5,1,2,3,4}.

Test case 2:

One possible path giving maximum product is {2,1,5}{2,1,5}.

Leave a Comment