Est is a super cute sword spirit that belongs to Kamito. One day, she goes for a walk with him in a spirit forest in Astral Zero. Est quickly realizes that this forest has many clearings and paths, and the clearings and paths actually form a tree structure.
There are 
~N~ clearings numbered from 
~1~ to ~N~ and 
~N-1~ paths in the spirit forest, and between every pair of clearings, there is a unique simple path. In every clearing, there may be a demon spirit, which Est will immediately defeat as she is far superior than these lowly demon spirits. Est is eager to defeat some demon spirits, but there is a problem: she doesn't know which clearing she is in right now (although she memorized the layout of the forest). For lack of a better option, Est decides to just keep moving from her current location without walking over the same path more than once and fight every demon spirit she meets along the way. Est may decide to stop at a clearing at any time during this journey. The path will visit at least two clearings, including the one Est starts at.
A path between clearings 
~i~ and 
~j~ 
~(i < j)~ is considered good if for two parameters 
~a~ and 
~b~ 
~(0 \le a \le b \le N)~ there are at least ~a~ demon spirits and at most ~b~ demon spirits on the simple path between ~i~ and ~j~. Est will enjoy herself the most if the path she chooses is a good path. Thus, she has 
~Q~ questions: given parameters ~a~ and ~b~, what is the probability that the path she takes is a good path?
Est is quite kind, and as such, she does not want you to deal with incredibly small real numbers. Therefore, if 
~p~ is the probability, you should output 
~p \cdot \dfrac{N \cdot (N-1)}{2}~. This comes from the fact that the probability of choosing a good path is the number of good paths divided by the total number of paths. Since Est does not know where she is initially, we should assume each clearing has a 
~\dfrac{1}{N}~ chance of being Est's initial clearing. Since Est's will cannot be predicted by mere humans, we should also assume each clearing that is not the initial clearing has a 
~\dfrac{1}{N-1}~ chance of being chosen as the final clearing where Est stops. In other words, you will just need to output the number of distinct good paths in the spirit forest for every ~a~ and ~b~ Est asks you. In particular, a path is considered distinct from another path if one path visits a clearing that the other path doesn't. Therefore, there are 
~\dfrac{N \cdot (N-1)}{2}~ distinct paths in total.
Note: Demon spirits don't move from their initial clearings.
Input Specification
The first line of input will have ~N~.
The second line of input will have ~N~ space-separated digits, either 
~0~ or ~1~. If and only if the 
~i^{th}~ number is ~1~, the ~i^{th}~ clearing has a demon spirit.
The next ~N-1~ lines describe the spirit forest. Each line is in the form 
~u\ v~ which means that clearings 
~u~ and 
~v~ are directly connected.
The 
~(N+2)^{th}~ line will have ~Q~.
The next ~Q~ lines each have ~a~ and ~b~, separated by a single space.
Output Specification
There should be ~Q~ lines of output, the answers to Est's questions. You should output the answers to Est's questions in the order that they are given.
Constraints
Subtask 1 [1%]
~2 \le N \le 50~
~1 \le Q \le 100~
Subtask 2 [2%]
~2 \le N \le 500~
~1 \le Q \le 200\,000~
Subtask 3 [2%]
~2 \le N \le 2\,000~
~1 \le Q \le 200\,000~
Subtask 4 [10%]
~2 \le N \le 100\,000~
~1 \le Q \le 200\,000~
~b \le 2~
Subtask 5 [15%]
~2 \le N \le 100\,000~
~1 \le Q \le 200\,000~
~b \le 3~
Subtask 6 [15%]
~2 \le N \le 100\,000~
~1 \le Q \le 3~
~b-a \le 10~
Subtask 7 [25%]
~2 \le N \le 40\,000~
~1 \le Q \le 100\,000~
Subtask 8 [30%]
~2 \le N \le 100\,000~
~1 \le Q \le 200\,000~
Sample Input
8
0 1 1 1 1 0 0 1
2 1
3 1
4 1
5 4
6 5
7 4
8 4
3
0 8
1 2
3 3
Sample Output
28
20
8
Comments
Can she defeat demons more than once? Also, can she visit the same clearing more than once?
This comment is hidden due to too much negative feedback. Show it anyway.
It is mentioned in the question that demon spirits reside on paths, and a good path is a path where the demon spirits on the path are within the condition a < demons < b. However, later on it says that demon spirits dont move from their clearings. How do I know how many demon spirits are on a given path?
Real talk I think you should start with some easier problems like Arrow.