Binary path queries

★★★★★

3.2

4 votes

Dynamic Programming, Modular arithmetic, Implementation, Trees, Data Structures, C++, Lowest Common Ancestor, Bit manipulation

Details

Submissions

Discussion

Editorial

Problem

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$

Time Limit: 4

Memory Limit: 256

Source Limit:

Explanation

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.