# Google Kick Start Archive — Round H 2021 problems

## Overview

Thank you for participating in Kick Start 2021 Round H!

Cast

Transform the String: Written by Bartosz Kostka and prepared by Chu-ling Ko.

Painter: Written by Bartosz Kostka and prepared by Jared Gillespie.

Silly Substitutions: Written by Kevin Tran and prepared by Nikolai Artemiev.

Dependent Events: Written by Siddharth Nayyar and prepared by Lucas Maciel.

Solutions, other problem preparation, reviews and contest monitoring by Alan Lou, Anson Ho, Anurag Singh, Anushi Maheshwari, Bartosz Kostka, Bianca Shimizu Oe, Bohdan Pryshchenko, Brijesh Panara, Chu-ling Ko, Chun-nien Chan, Cristhian Bonilha, Deeksha Kaurav, Duong Hoang, Federico Brubacher, Guilherme Rodrigues Nogueira de Souza, Hsin-Yi Wang, Jakub Kuczkowiak, Jared Gillespie, Kashish Bansal, Kevin Tran, Laksh Nachiappan, Lizzie Sapiro Santor, Lucas Maciel, Maneeshita Sharma, Michał Łowicki, Mohamed Yosri Ahmed, Motty Porat, Nikolai Artemiev, Phil Sun, Rahul Goswami, Rishabh Agarwal, Robert O'Connor, Ruoyu Zhang, Samiksha Gupta, Sarah Young, Shahed Shahriar, Shubham Garg, Shweta Karwa, Siddharth Nayyar, Subhasmita Sahoo, Surya Upadrasta, Swapnil Gupta, Swapnil Mahajan, Swetank Modi, Tarun Khullar, Teja Vardhan Reddy Dasannagari, Umang Goel, Vijay Krishan Pandey, Wendi Wang, Yulian Yarema, Zhitao Li.

Analysis authors:

• Transform the String: Deeksha Kaurav
• Painter: Vijay Krishan Pandey
• Silly Substitutions: Motty Porat
• Dependent Events: Phil Sun

## A. Transform the String

### Problem

You are given a string $$\mathbf{S}$$$which denotes a padlock consisting of lower case English letters. You are also given a string $$\mathbf{F}$$$ consisting of set of favorite lower case English letters. You are allowed to perform several operations on the padlock. In each operation, you can change one letter of the string to the one following it or preceding it in the alphabetical order. For example: for the letter c, you are allowed to change it to either b or d in an operation. The letters can be considered in a cyclic order, i.e., the preceding letter for letter a would be letter z. Similarly, the following letter for letter z would be letter a.

Your aim is to find the minimum number of operations that are required such that each letter in string $$\mathbf{S}$$$after applying the operations, is present in string $$\mathbf{F}$$$.

### Input

The first line of the input gives the number of test cases, $$\mathbf{T}$$$. $$\mathbf{T}$$$ test cases follow.

Each test case consists of two lines.
The first line of each test case contains the string $$\mathbf{S}$$$. The second line of each test case contains the string $$\mathbf{F}$$$.

### Output

For each test case, output one line containing Case #$$x$$$: $$y$$$, where $$x$$$is the test case number (starting from 1) and $$y$$$ is the minimum number of operations that are required such that each letter in string $$\mathbf{S}$$$after applying the operations, is one of the characters in string $$\mathbf{F}$$$.

### Limits

Memory limit: 1 GB.
$$1 \le \mathbf{T} \le 100$$$. $$1 \le$$$ the length of $$\mathbf{S} \le 10^5$$$. $$\mathbf{S}$$$ only consists of lower case English letters.
$$\mathbf{F}$$$only consists of distinct lower case English letters. The letters in string $$\mathbf{F}$$$ are lexicographically sorted.

#### Test Set 1

Time limit: 20 seconds.

## B. Painter

### Problem

You have recently started to study how to paint, and in one of the first classes you learned about the three primary colors: Red, Yellow, and Blue. If you combine these colors, you can produce many more colors. For now, the combinations that you have studied are the following:

• Red + Yellow = Orange
• Red + Blue = Purple
• Yellow + Blue = Green
• Red + Yellow + Blue = Gray

You still do not understand shades of colors, therefore the proportion and order of each color in the combination does not matter. For example, combining Red and Yellow produces the same result as combining Yellow and Red, as well as the same result as combining Red, Yellow, and Red again.

To practice your skills, you want to paint a 1-dimensional painting $$\mathbf{P}$$$of length $$\mathbf{N}$$$. Your painting consists of $$\mathbf{N}$$$squares. From left to right, $$\mathbf{P_i}$$$ represents the color of the i-th square. Initially all squares are Uncolored, that is, $$\mathbf{P_i}$$$= Uncolored for every $$1 \le i \le \mathbf{N}$$$.

In a single stroke, you can choose one of the three primary colors and apply it to a sequence of consecutive squares. In other words, you can choose a color $$c$$$and two integers $$l$$$ and $$r$$$, such that $$1 \le l \le r \le \mathbf{N}$$$, and apply color $$c$$$to all squares $$\mathbf{P_j}$$$ such that $$l \le j \le r$$$. If the square being painted is currently Uncolored, then its color will become $$c$$$. Otherwise, the color will be a combination of all the colors applied on this square so far and the new color $$c$$$, as described in the list above. In order to save time, you want to use as few strokes as possible. Given the description of the painting that you want to paint, figure out what is the minimum number of strokes required to paint it. ### Input The first line of the input gives the number of test cases, $$\mathbf{T}$$$. $$\mathbf{T}$$$test cases follow. Each test case starts with a line containing an integer $$\mathbf{N}$$$, representing the length of the painting. Then on the next line, there will be a string $$\mathbf{P}$$$of length $$\mathbf{N}$$$, representing the painting. The $$i$$$-th character represents the color of square $$\mathbf{P_i}$$$, according to the following list:

• U = Uncolored
• R = Red
• Y = Yellow
• B = Blue
• O = Orange
• P = Purple
• G = Green
• A = Gray

### Output

For each test case, output one line containing Case #$$x$$$: $$y$$$, where $$x$$$is the test case number (starting from 1) and $$y$$$ is the minimum number of strokes required to paint the painting.

### Limits

Memory limit: 1 GB.
$$1 \le \mathbf{T} \le 100$$$. $$1 \le \mathbf{N} \le 10^5$$$.

#### Test Set 1

Time limit: 20 seconds.

### Sample

Note: there are additional samples that are not run on submissions down below.
Sample Input
2
9
YYYBBBYYY
6
YYGGBB

Sample Output
Case #1: 3
Case #2: 2


In Sample Case #1, the solution is to make $$3$$$strokes: the first one using color Yellow from square $$1$$$ through $$3$$$, the second one using color Blue from square $$4$$$ through $$6$$$, and the third one using color Yellow from square $$7$$$ through $$9$$$. Notice that this particular painting required only primary colors. In Sample Case #2, the solution is to make $$2$$$ strokes: the first one using color Yellow from square $$1$$$through $$4$$$, and the second one using color Blue from square $$3$$$through $$6$$$. Notice that squares $$3$$$and $$4$$$ will be painted with both colors Yellow and Blue, which will result on it being Green.

### Additional Sample - Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.
Sample Input
1
5
ROAOR

Sample Output
Case #1: 3


Your task is to find how the final string will look like for the given $$\mathbf{S}$$$. ### Input The first line of the input gives the number of test cases, $$\mathbf{T}$$$. $$\mathbf{T}$$$test cases follow. Each test case consists of two lines. The first line of each test case contains an integer $$\mathbf{N}$$$, denoting the length of the string $$\mathbf{S}$$$. The second line of each test case contains a string $$\mathbf{S}$$$ of length $$\mathbf{N}$$$. ### Output For each test case, output one line containing Case #$$x$$$: $$y$$$, where $$x$$$ is the test case number (starting from 1) and $$y$$$is the final string obtained. ### Limits Memory limit: 1 GB. $$1 \le \mathbf{T} \le 100$$$.
The input string only consists of digits 0-9.

#### Test Set 1

Time limit: 20 seconds.
$$1 \le \mathbf{N} \le 100$$$. #### Test Set 2 Time limit: 60 seconds. For at most 10 cases: $$1 \le \mathbf{N} \le 5 \times 10^5$$$.
For the remaining cases:

### Input

The first line of the input gives the number of test cases, $$\mathbf{T}$$$. $$\mathbf{T}$$$ test cases follow.

The first line of each test case contains two integers $$\mathbf{N}$$$and $$\mathbf{Q}$$$ denoting the number of events and number of queries, respectively. $$\mathbf{N}$$$lines follow. The $$i$$$-th line describes event $$i$$$. The first line contains a single integer $$\mathbf{K}$$$ denoting the probability of occurrence of event $$1$$$multiplied by $$10^6$$$. Each of the next $$\mathbf{N}-1$$$lines consists of three integers $$\mathbf{P_{i}}$$$, $$\mathbf{A_{i}}$$$and $$\mathbf{B_{i}}$$$ denoting the parent event of event $$i$$$, the probability of occurrence of event $$i$$$ if its parent event occurs multiplied by $$10^6$$$, and the probability of occurrence of event $$i$$$ if its parent event does not occur multiplied by $$10^6$$$, respectively. Then, $$\mathbf{Q}$$$ lines follow, describing the queries. Each of these lines contains two distinct integers $$\mathbf{u_{j}}$$$and $$\mathbf{v_{j}}$$$. For each query, find the probability that both events $$\mathbf{u_{j}}$$$and $$\mathbf{v_{j}}$$$ occurred.

For each test case, output one line containing Case #$$x$$$: $$R_{1} \ R_{2} \ R_{3} \ \dots \ R_{Q}$$$, where $$x$$$ is the test case number (starting from 1) and $$R_{j}$$$ is the sought probability computed for $$j$$$-th query modulo $$10^9+7$$$, which is defined precisely as follows. Represent the answer of $$j$$$-th query as an irreducible fraction $$\frac{p}{q}$$$. The number $$R_{j}$$$then must satisfy the modular equation $$R_{j} \times q \equiv p \pmod{(10^{9} + 7)}$$$, and be between $$0$$$and $$10^9+6$$$, inclusive. It can be shown that under the constraints of this problem such a number $$R_{j}$$$always exists and is uniquely determined. ### Limits Time limit: 60 seconds. Memory limit: 1 GB. $$1 \le \mathbf{T} \le 100$$$.
$$1 \le \mathbf{P_{i}} \lt \mathbf{i}$$$, for each $$i$$$ from $$2$$$to $$\mathbf{N}$$$.
$$1 \le \mathbf{u_{j}}, \mathbf{v_{j}} \le \mathbf{N}$$$and $$\mathbf{u_{j}} \neq \mathbf{v_{j}}$$$, for all $$j$$$. $$0 \le \mathbf{A_{i}} \le 10^6$$$, for each $$i$$$from $$2$$$ to $$\mathbf{N}$$$. $$0 \le \mathbf{B_{i}} \le 10^6$$$, for each $$i$$$from $$2$$$ to $$\mathbf{N}$$$. $$0 \le \mathbf{K} \le 10^6$$$.

#### Test Set 1

$$2 \le \mathbf{N} \le 1000$$$. $$1 \le \mathbf{Q} \le 1000$$$.

#### Test Set 2

For at most 5 cases:
$$2 \le \mathbf{N} \le 2 \times 10^{5}$$$. $$1 \le \mathbf{Q} \le 2 \times 10^{5}$$$.

For the remaining cases:
$$2 \le \mathbf{N} \le 1000$$$. $$1 \le \mathbf{Q} \le 1000$$$.

### Sample

Sample Input
2
5 2
200000
1 400000 300000
2 500000 200000
1 800000 100000
4 200000 400000
1 5
3 5
4 2
300000
1 100000 100000
2 300000 400000
3 500000 600000
1 2
2 4

Sample Output
Case #1: 136000001 556640004
Case #2: 710000005 849000006


For Sample Case #1, for the first query, the probability that both events $$1$$$and $$5$$$ occurred is given by (the probability that event $$1$$$occurred) $$\times$$$ (probability that event $$5$$$occurs given event $$1$$$ occurred). Event $$1$$$would occur with probability $$0.2$$$. Given that event $$1$$$occurred, the probability that event $$4$$$ occurs is $$0.8$$$. Therefore, the probability of occurrence of event $$5$$$ given that event $$1$$$occurred is $$0.2 \times 0.8 + 0.4 \times 0.2 = 0.24$$$ (probability of event $$5$$$occurring given than event $$4$$$ occurred $$+$$$probability of event $$5$$$ occurring given that event $$4$$$did not occur). The probability that both events $$1$$$ and $$5$$$occurred is $$0.2 \times 0.24 = 0.048$$$. The answer $$0.048$$$can be converted into fraction of $$\frac{6}{125}$$$, and one can confirm that the $$136000001$$$satisfies the conditions mentioned in the output section as $$136000001 \times 125 \equiv 6 \pmod{ (10^{9} + 7)}$$$ and is uniquely determined. For the second query, the probability that both events $$5$$$and $$3$$$ occurred is $$0.10352$$$. For Sample Case #2, for the first query, the probability that both events $$1$$$ and $$2$$$occurred is given by (the probability that event $$1$$$ occurred) $$\times$$$(probability that event $$2$$$ occurs given event $$1$$$occurred). As $$1$$$ is the parent event of event $$2$$$, the probability of event $$2$$$ occurring given event $$1$$$occurred is $$\mathbf{A_{2}}$$$ which is $$0.1$$$. Hence, the probability that both events $$1$$$ and $$2$$$occurred is $$0.3 \times 0.1$$$. Hence, the output will be $$3 \times 10^{-2} \bmod (10^9+7) = 710000005$$$. For the second query, the probability of occurrence of both events $$2$$$ and $$4$$$is $$0.057$$$.

## Analysis — A. Transform the String

Let us first define the two operations that we can perform.

• Clockwise: Changing a letter to the one following it. For example, changing from c to d.
• Counter-clockwise: Changing a letter to the one preceding it. For example, changing from a to z.

Let us denote the ASCII value of a character $$c_x$$$by $$ASCII(c_x)$$$. If we move the padlock from a character $$c_a$$$to another character $$c_b$$$ such that $$ASCII(c_a) < ASCII(c_b)$$$, the number of operations required in clockwise direction = $$ASCII(c_b) - ASCII(c_a)$$$ and the number of operations required in counter-clockwise direction = $$26 - (ASCII(c_b) - ASCII(c_a))$$$. For example, if we move the padlock from c to e: • Number of operations required in clockwise direction = $$ASCII(e) - ASCII(c) = 2$$$.
• Number of operations required in counter-clockwise direction = $$26 - (ASCII(e) - ASCII(c)) = 24$$$. Similarly, if we move the padlock from a character $$c_a$$$ to another character $$c_b$$$such that $$ASCII(c_a) > ASCII(c_b)$$$, the number of operations required in clockwise direction = $$26 - (ASCII(c_a) - ASCII(c_b))$$$and the number of operations required in counter-clockwise direction = $$ASCII(c_a) - ASCII(c_b))$$$.

For example, if we move the padlock from g to b:

• Number of operations required in clockwise direction = $$26 - (ASCII(g) - ASCII(b)) = 21$$$. • Number of operations required in counter-clockwise direction = $$ASCII(g) - ASCII(b) = 5$$$.

Thus minimum number of operations required to change a character in the padlock from $$c_a$$$to $$c_b$$$ = $$min(abs(ASCII(c_a) - ASCII(c_b)), 26 - abs(ASCII(c_a) - ASCII(c_b)))$$$. Let us call the above expression $$f(c_a, c_b)$$$.

### Approach 1

When length of $$\mathbf{F}$$$= $$1$$$ we need to change every character in $$\mathbf{S}$$$to that in $$\mathbf{F}$$$. Therefore, the answer is the sum of $$f(c_s, c_f)$$$for every character $$c_s$$$ in $$\mathbf{S}$$$and $$c_f$$$ in $$\mathbf{F}$$$. #### Test Set 2 For this case, $$\mathbf{F}$$$ can have multiple characters.

For each character in $$\mathbf{S}$$$we need to find a character in $$\mathbf{F}$$$ such that $$f(c_s, c_f)$$$is minimized. Therefore, for every character $$c_s$$$ in $$\mathbf{S}$$$, we iterate over all possible characters $$c_f$$$ in $$\mathbf{F}$$$and find minimum of $$f(c_s, c_f)$$$ and add the minimum value to the final answer.

### Approach 2

For each character in $$\mathbf{S}$$$, move the padlock in the clockwise direction and count the number of operations until we reach a character that belongs to $$\mathbf{F}$$$. Similarly, for the same character in $$\mathbf{S}$$$, move the padlock in the counter-clockwise direction and count the number of operations until we reach a character that belongs to $$\mathbf{F}$$$. Compare the number of operations in both directions and add minimum of the two to the final answer.

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Analysis — B. Painter

Given the three primary colors: Red, Yellow, and Blue, we need to determine the minimum number of strokes required to paint a 1-dimensional painting $$\mathbf{P}$$$of length $$\mathbf{N}$$$. In $$1$$$stroke, you can choose a color either Red, Yellow, or Blue, and two integers $$l$$$ and $$r$$$, such that $$1 \le l \le r \le \mathbf{N}$$$, and apply the chosen color to all squares $$\mathbf{P_j}$$$such that $$l \le j \le r$$$.

Note as the colors: Red, Yellow, and Blue are independent of each other and the proportion and order of each color in the combination does not matter, the minimum number of strokes to complete the paining will be the minimum number of Red strokes $$+$$$minimum number of Blue strokes $$+$$$ minimum number of Yellow strokes.

Let $$F(x)$$$be the minimum number of strokes needed of primary color $$x$$$. Notice minimum number of strokes of $$x$$$is same as number of continuous blocks of squares that will need the primary color $$x$$$ to form the required color. To find $$F(x)$$$we will start from the leftmost end of the squares. Whenever we encounter a square either with the color $$x$$$ or with some color $$y$$$which is a combination of $$x$$$ and other primary colors, we paint the squares with the color $$x$$$in $$1$$$ stroke until we reach the rightmost end, or some color $$y$$$which is neither $$x$$$ nor a combination of $$x$$$and any other primary color. We continue this until we have encountered all the squares. The number of strokes used is equal to $$F(x)$$$.

### Test Set 1

We are given that $$\mathbf{P_i}$$$will be one of {$$Y, B, G$$$}. The final answer will be $$F(Yellow) + F(Blue)$$$. Complexity : $$O(\mathbf{N})$$$ per test case

### Test Set 2

We are given that $$\mathbf{P_i}$$$will be one of {$$U, R, Y, B, O, P, G, A$$$}. The final answer will be $$F(Red) + F(Yellow) + F(Blue)$$$. Complexity : $$O(\mathbf{N})$$$ per test case

##### Sample Code(C++)

int minimum_number_of_strokes_for_primary_color_x(string S, int N, char x, map<char, string> color_to_primary_colors_mapping) {
int min_strokes = 0;
int last_stroke_position = INT_MIN;
for(int i = 0; i < N; i++) {
if (S[i] == 'U') {
continue;
}
if(S[i] == x || color_to_primary_colors[S[i]].find(x) != string::npos) {
if (last_stroke_position != i - 1) {
min_strokes++;
}
last_stroke_position = i;
}
}
return min_strokes;
}

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Analysis — C. Silly Substitutions

Therefore, complexity: $$O(\mathbf{N} ^ 2)$$$per test case. ### Test Set 2 To reduce the complexity we should implement our own "replace all" and optimize the two things that it does: • Instead of searching the entire string every time, we will maintain a set of "locations of interest". More accurately, 10 sets: all locations of the substring 01, all locations of the substring 12, and so on. How to define a location in a string that keeps changing? The next bullet solves this. • To quickly replace characters, we will convert the string to a bidirectional linked list where each node holds a character. Thus, a location in the string is actually a pointer to a node, and each local change, such as removing two nodes or inserting a node, takes $$O(1)$$$ time.

A "replace all" operation might still take linear time in the optimized version. For example, if $$\mathbf{S} =$$$010101010101 then the first replacement (of all the 01s to 2s) will have to replace $$\mathbf{N}/2$$$ occurrences. But then, the next operations will be either few enough or fast enough to compensate for the long one. This is known as amortized analysis.

More accurately, whenever a location becomes interesting, one of the future replacement operations will have to handle it (as said, by $$O(1)$$$manipulations of the linked list). How many times can locations become interesting? In the initial string, maybe all the $$\mathbf{N}$$$ characters (except the last one) start as interesting. Later on, whenever we replace a pair of characters with a new one, that new character may turn one or both its neighbors to be interesting. For example, when changing 1013 to 123 it creates two interesting substrings: 12 and 23. Finer analysis can show that we only need to mark the 12 as interesting, but it does not really matter for our conclusion.

So, since we replace characters at most $$\mathbf{N}$$$times, the event of a location becoming interesting can happen at most $$3\mathbf{N}$$$ times (or $$2\mathbf{N}$$$with finer analysis). Therefore, complexity: $$O(\mathbf{N})$$$ per test case

Notes:

1. We can even mark "false interesting locations". That is, mark all the initial locations and both neighbors of every modification as interesting, even if they do not really start a pair that should be replaced (like 01). Of course, our "replace all" operation will need to check if each "interesting location" should indeed be replaced, but this is a good practice anyway. The best part is that our analysis with the $$3\mathbf{N}$$$bound will still be valid. 2. The set of locations of interest is indeed a set - each location should be marked once and the order that we handle them does not matter. However, if your programming language makes it harder (higher complexity) to maintain a set, you may as well store the locations of interest in any other structure, like a vector or a list. Test Data info We recommend that you practice debugging solutions without looking at the test data. ## Analysis — D. Dependent Events For this problem, we are given a graphical model in the form of a directed, rooted tree, where each vertex is an event. For any vertex $$v$$$ on this tree, let $$v=0$$$and $$v=1$$$ denote the non-occurrence and occurrence of event $$v$$$, respectively. Let $$l_j$$$ be the lowest common ancestor (LCA) of $$\mathbf{u_j}$$$and $$\mathbf{v_j}$$$. By the total probability rule, $$P[\mathbf{u_j}=1, \mathbf{v_j}=1]=\sum_{i=0}^1 P[\mathbf{u_j}=1, \mathbf{v_j}=1, l_j=i]$$$. We know $$\mathbf{u_j}$$$ and $$\mathbf{v_j}$$$are conditionally independent given $$l_j$$$, because the paths $$l_j\rightarrow \mathbf{u_j}$$$and $$l_j\rightarrow \mathbf{v_j}$$$ are edge-disjoint due to the definition of LCA. This allows us to simplify the earlier sum into $$\sum_{i=0}^1 P[\mathbf{u_j}=1 | l_j=i]P[\mathbf{v_j}=1 | l_j = i]P[l_j=i]$$$. This formula forms the basis of our solution, and the approaches for the two test sets differ only in how to compute the required probabilities efficiently. To deal with the output format of this problem, we store all results as fractions and take the numerator and denominator modulo $$10^9+7$$$ after each operation to avoid overflow. If our final result is $$\frac{p}{q}$$$, we output $$pq^{-1}\pmod{10^9+7}$$$. Due to the nature of the problem, $$q$$$will always be a power of ten, so the inverse is guaranteed to exist, and can be efficiently computed via extended Euclidean algorithm. Alternatively, due to Fermat's little theorem, we can equivalently raise $$q$$$ to the $$(10^9+5)$$$-th power to find its inverse; this can be done efficiently with exponentiation by squaring. ### Test set 1 For this test set it suffices to naively compute $$l_j$$$. We can then compute $$P[\mathbf{u_j}=1|l_j]$$$and $$P[\mathbf{v_j}=1|l_j]$$$ by walking back down the tree from $$l_j$$$. To do this, we can use the total probability rule similar to before; if $$p(x)$$$ denotes the parent of $$x$$$, then $$P[x=1 | l_j=i] = \sum_{k=0}^1P[x=1,p(x)=k | l_j=i] = \sum_{k=0}^1 P[x=1 | p(x)=k]P[p(x)=k | l_j = i]$$$; note that the first term in this product comes from the input, and the second term comes from the previous step of our walk. We can use the same formula to compute $$P[l_j=i]$$$, since $$P[l_j=i]=\sum_{k=0}^1P[l_j=i|r=k]P[r=k]$$$, where $$r$$$is the root of the tree. Each vertex is visited at most $$O(1)$$$ times per query using this technique, so our overall time complexity is $$O(\mathbf{NQ})$$$per test case, which is sufficient. ### Test set 2 There are both more queries and a larger tree in this test set, so the naive solution is too slow. This test set requires computing $$l_j$$$, the LCA of $$\mathbf{u_j}$$$and $$\mathbf{v_j}$$$, in $$O(\log \mathbf{N})$$$time anyways, so we can think of ways to augment an LCA algorithm to also keep track of the necessary probabilities for us. For example, the binary lifting LCA algorithm pre-computes $$p^i(v)$$$ for all vertices $$v$$$, where $$p^i(\cdot)$$$ gives the $$2^i$$$-th parent of a given vertex. We can extend the binary lifting algorithm to not only store the id of this parent, but to also store $$P[v=1|p^i(v)]$$$. These probabilities can then be multiplied such that only $$O(\log \mathbf{N})$$$hops are needed to get from $$\mathbf{u_j}$$$ or $$\mathbf{v_j}$$$up to $$l_j$$$. The unconditional probability $$P[l_j]$$$can simply be pre-computed for the entire tree via DFS in $$O(\mathbf{N})$$$ time. This allows us to answer each query in $$O(\log \mathbf{N})$$$time, so our overall time complexity is $$O(\mathbf{N}\log \mathbf{N}+\mathbf{Q}\log \mathbf{N})$$$ per test case.

Test Data
info We recommend that you practice debugging solutions without looking at the test data.