JONTRONA RUET CodeSmash 2020
Limits 1.5s, 512 MB

Your friend has come to visit the RUET campus. As the Mango season goes on \cdots, he/she said “Mama Aam Khawa!”. As Manik Bhai leased those Mango Trees, he will not give you guys Mangoes for free rather he gave you a problem as he knew you are a great problem solver. You and your friend want one mango for each but with Distinction. The Distinction means bitwise XORXOR of the sweetness of mangoes must be positive (greater than zero). There will be multiple queries.

Given a Mango Tree rooted at node 11. Each node represents a Mango with sweetness SiS_i. Manik bhai will only let you choose mangoes from a subtree. So, in each query, Manik bhai will give you a node UU and you just need to find - in the subtree rooted at UU, how many ways you can take two mangoes such that they have Distinction.

A subtree of a tree is a tree that consists of a node in the tree and all of this node's descendants. The tree can also be considered as a subtree of itself.


The first line of the input will have NN (1N5×1051 \leq N \leq 5 \times 10^5) and QQ (1Q5×1051 \leq Q \leq 5 \times 10^5), number of Mangoes in the Tree and number of queries respectively.

Then the next line contains N numbers in form SiS_i (1Si23111 \leq S_i \leq {2^{31} -1}), the sweetness of the ii-th mango.

Next N1N - 1 lines, each containing aa (1aN1\leq a\leq N) and bb (1bN1\leq b\leq N) as there is a branch between node aa and bb. It’s guaranteed that they will form a Tree.

The next line contains QQ numbers, indicating UU, the root of the Subtree for each query.


For each query, print the answer of the Query. As the answer can be too large print modulo 10000000071000000007.


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


Login to submit.


67% Solution Ratio
mahabub.tweetEarliest, 8M ago
steinumFastest, 0.7s
steinumLightest, 86 MB
steinumShortest, 1556B
Toph uses cookies. By continuing you agree to our Cookie Policy.