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.
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.
Scoring for this problem is Binary, that means you have to pass all the test cases to get a positive score.
For each query, print the count of ordered pairs of integers satisfying the four given conditions on a new line.