- Prepare
- Data Structures
- Advanced
- Counting On a Tree

# Counting On a Tree

# Counting On a Tree

- Prepare
- Data Structures
- Advanced
- Counting On a Tree

Taylor loves trees, and this new challenge has him stumped!

Consider a tree, , consisting of nodes. Each node is numbered from to , and each node has an integer, , attached to it.

A *query* on tree takes the form `w x y z`

. To process a query, you must print the count of ordered pairs of integers such that the following four conditions are all satisfied:

- the path from node to node .
- path from node to node .

Given and queries, process each query in order, printing the pair count for each query on a new line.

**Input Format**

The first line contains two space-separated integers describing the respective values of (the number of nodes) and (the number of queries).

The second line contains space-separated integers describing the respective values of each node (i.e., ).

Each of the subsequent lines contains two space-separated integers, and , defining a bidirectional edge between nodes and .

Each of the subsequent lines contains a `w x y z`

query, defined above.

**Constraints**

Scoring for this problem is Binary, that means you have to pass all the test cases to get a positive score.

**Output Format**

For each query, print the count of ordered pairs of integers satisfying the four given conditions on a new line.

**Sample Input**

```
10 5
10 2 3 5 10 5 3 6 2 1
1 2
1 3
3 4
3 5
3 6
4 7
5 8
7 9
2 10
8 5 2 10
3 8 4 9
1 9 5 9
4 6 4 6
5 8 5 8
```

**Sample Output**

```
0
1
3
2
0
```

**Explanation**

We perform queries on the following tree:

- Find the number of valid ordered pairs where is in the path from node to node and is in the path from node to node . No such pair exists, so we print .
- Find the number of valid ordered pairs where is in the path from node to node and is in the path from node to node . One such pair, , exists, so we print .
- Find the number of valid ordered pairs where is in the path from node to node and is in the path from node to node . Three such pairs, , , and exist, so we print .
- Find the number of valid ordered pairs where is in the path from node to node and is in the path from node to node . Two such pairs, and , exist, so we print .
- Find the number of valid ordered pairs where is in the path from node to node and is in the path from node to node . No such pair exists, so we print .