Terminus Est

View as PDF

Points: 35 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem types

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 clearings numbered from to and 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 and is considered good if for two parameters and there are there are at least demon spirits and at most demon spirits on the simple path between and . Est will enjoy herself the most if the path she chooses is a good path. Thus, she has questions: given parameters and , 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 is the probability, you should output . 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 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 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 and 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 distinct paths in total.

Note: Demon spirits don't move from their initial clearings.

Input Specification

The first line of input will have .

The second line of input will have space-separated digits, either or . If and only if the number if , the clearing has a demon spirit.

The next lines describe the spirit forest. Each line in the form which means that clearings and are directly connected.

The line will have .

The next lines each have and , separated by a single space.

Output Specification

There should be 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.

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

• commented on Nov. 20, 2020, 11:36 p.m. edited

Can she defeat demons more than once? Also, can she visit the same clearing more than once?

• commented on Nov. 25, 2015, 3:37 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Nov. 25, 2015, 12:01 p.m.

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?

• commented on Nov. 25, 2015, 5:21 p.m.

Real talk I think you should start with some easier problems like Arrow.