You are given a tree $$G$$ consisting of $$N$$ nodes. The $$i^{th}$$($$1 \leq i \leq N $$) node of the tree has been assigned a binary value $$A_i$$, that is $$A_i = 0/1$$. You are also given $$Q$$ queries.
In each query, you are given 2 nodes $$u$$ and $$v$$. Initialize an empty string. Now, consider the simple path between these 2 nodes(from $$u$$ to $$v$$) and append the binary values obtained on this path to the string. Your task is to find the decimal representation of this binary string. Note that the bit at $$v$$ corresponds to LSB.
Since the output can be very large, you need to calculate the decimal representation modulo $$1000000007$$ $$(10^9+7)$$
You are given $$T$$ test cases.
Warning: Use FAST I/O Methods.
Input format
- The first line contains a single integer $$T$$ denoting number of test cases.
- For each test case:
- The first line contains an integer $$N$$ denoting the number of nodes in tree.
- Second line contains $$N$$ space separated integers denoting the values of the nodes.
- Next $$N-1$$ lines follow. For each line:
- Two space-separated integers $$u$$ and $$v$$ denoting the nodes of the tree. This means there is an edge between node $$u$$ and $$v$$.
- Next line contains $$Q$$ denoting the number of queries.
- $$Q$$ lines follow. Each line contains 2 space separated integers $$u$$ and $$v$$.
Output format
For each test case(in a separate line), output(in a separate line) $$Q$$ space separated integers where the $$i^{th}$$ integer denotes the decimal representation of the binary string obtained on the simple path between the two vertices in the $$i^{th}$$ query. Don't forget to take modulo $$1000000007$$ $$(10^9+7)$$
Constraints
$$ 1 \le T \le 1000 \\
1 \leq N, Q \leq 5 \times 10^5 \\
0 \leq A_i \leq 1 \\
1 \le u, v \le N \\
\text{It is guaranteed that given edges form a tree} \\
\text{Sum of N over all test cases does not exceed } 5 \times 10^5 \\
\text{Sum of Q over all test cases does not exceed } 5 \times 10^5 $$
2 6 1 0 1 0 1 1 1 2 1 5 5 6 2 4 2 3 3 3 6 4 5 1 6 2 1 1 1 2 2 1 2 2 2
23 3 7 3 1
In the first test case, we have $$N = 6, A = [1, 0, 1, 0, 1, 1], Q = 3$$. The tree is shown below:
We now answer the queries:
- First query: $$ u = 3, v = 6$$. The path is $$3\text{ } ->2\text{ } ->1\text{ } ->5\text{ } ->6$$, the binary string is $$10111$$. The decimal representation is $$23$$.
- Second query: $$ u = 4, v = 5$$. The path is $$4\text{ } ->2\text{ } ->1\text{ } ->5$$, the binary string is $$0011$$. The decimal representation is $$3$$.
- Third query: $$ u = 1, v = 6$$. The path is $$1\text{ } ->5\text{ } ->6$$, the binary string is $$111$$. The decimal representation is $$7$$.
- Note that we output answers in a single line.
In the second test case, we have $$N = 2, A = [1, 1], Q = 2$$. The tree is shown below:
We now answer the queries:
- First query: $$ u = 1, v = 2$$. The path is $$1\text{ } ->2$$, the binary string is $$11$$. The decimal representation is $$3$$.
- Second query: $$ u = 2, v = 2$$. The path is $$2$$, the binary string is $$1$$. The decimal representation is $$1$$.
- Note that we output answers in a single line.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor