STNBD P6 - Terminus Est - Olympiads Online Judge

STNBD P6 - Terminus Est

View as PDF

Submit solution

All submissions

Best submissions

Points: 35 (partial)

Time limit: 2.5s

Memory limit: 256M

Author:

FatalEagle

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 $N$ ~N~ clearings numbered from $1$ ~1~ to $N$ ~N~ and $N-1$ ~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$ ~i~ and $j$ ~j~ $(i < j)$ ~(i < j)~ is considered good if for two parameters $a$ ~a~ and $b$ ~b~ $(0 \le a \le b \le N)$ ~(0 \le a \le b \le N)~ there are at least $a$ ~a~ demon spirits and at most $b$ ~b~ demon spirits on the simple path between $i$ ~i~ and $j$ ~j~. Est will enjoy herself the most if the path she chooses is a good path. Thus, she has $Q$ ~Q~ questions: given parameters $a$ ~a~ and $b$ ~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$ ~p~ is the probability, you should output $p \cdot \dfrac{N \cdot (N-1)}{2}$ ~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}$ ~\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}$ ~\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$ ~a~ and $b$ ~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}$ ~\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$ ~N~.

The second line of input will have $N$ ~N~ space-separated digits, either $0$ ~0~ or $1$ ~1~. If and only if the $i^{th}$ ~i^{th}~ number is $1$ ~1~, the $i^{th}$ ~i^{th}~ clearing has a demon spirit.

The next $N-1$ ~N-1~ lines describe the spirit forest. Each line is in the form $u\ v$ ~u\ v~ which means that clearings $u$ ~u~ and $v$ ~v~ are directly connected.

The $(N+2)^{th}$ ~(N+2)^{th}~ line will have $Q$ ~Q~.

The next $Q$ ~Q~ lines each have $a$ ~a~ and $b$ ~b~, separated by a single space.

Output Specification

There should be $Q$ ~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$ ~2 \le N \le 50~

$1 \le Q \le 100$ ~1 \le Q \le 100~

Subtask 2 [2%]

$2 \le N \le 500$ ~2 \le N \le 500~

$1 \le Q \le 200\,000$ ~1 \le Q \le 200\,000~

Subtask 3 [2%]

$2 \le N \le 2\,000$ ~2 \le N \le 2\,000~

$1 \le Q \le 200\,000$ ~1 \le Q \le 200\,000~

Subtask 4 [10%]

$2 \le N \le 100\,000$ ~2 \le N \le 100\,000~

$1 \le Q \le 200\,000$ ~1 \le Q \le 200\,000~

$b \le 2$ ~b \le 2~

Subtask 5 [15%]

$2 \le N \le 100\,000$ ~2 \le N \le 100\,000~

$1 \le Q \le 200\,000$ ~1 \le Q \le 200\,000~

$b \le 3$ ~b \le 3~

Subtask 6 [15%]

$2 \le N \le 100\,000$ ~2 \le N \le 100\,000~

$1 \le Q \le 3$ ~1 \le Q \le 3~

$b-a \le 10$ ~b-a \le 10~

Subtask 7 [25%]

$2 \le N \le 40\,000$ ~2 \le N \le 40\,000~

$1 \le Q \le 100\,000$ ~1 \le Q \le 100\,000~

Subtask 8 [30%]

$2 \le N \le 100\,000$ ~2 \le N \le 100\,000~

$1 \le Q \le 200\,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

0

Ryan_Sharma commented on Nov. 18, 2024, 11:16 p.m.

How does one even find this?? No shot DMOJ is freaky now

6
defined commented on Nov. 18, 2024, 10:14 p.m.
Whoever did this has some explaining to do!!!

Paste the easter egg script into the console or the user-script:

$(function() { $(".anime-img").show(); });

In DevTools (Inspect Element), find the element with class anime-img by pressing ctrl+f and putting .anime-img. Expand the div and read over the alt attribute.

1

volcano commented on Nov. 18, 2024, 11:14 p.m.

Welcome to the Freaky Modern Online Judge

0

Viv_CCGS commented on Nov. 18, 2024, 10:42 p.m.

You have a lot of explaining to do.

0

defined commented on Nov. 18, 2024, 10:52 p.m.

I actually didn't find this specific one out so...

0

justin_g_20 commented on Nov. 21, 2020, 4:36 a.m. ← edited →

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

-10

XIAOAGE commented on Nov. 25, 2015, 8:37 p.m.

sword girl LOL

This comment is hidden due to too much negative feedback. Show it anyway.

-3

Elahrai commented on Nov. 25, 2015, 5: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?