1/23/25, 7:29 PM Problem - 2040E - Codeforces
|
stdfloat | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP RAYAN
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 992 (Div. 2)
E. Control of Randomness Finished
time limit per test: 2 seconds Practice
memory limit per test: 256 megabytes
You are given a tree with n vertices.
Let's place a robot in some vertex v ≠ 1, and suppose we initially have p coins. Consider the
following process, where in the i -th step (starting from i = 1 ):
→ Virtual participation
Virtual contest is a way to take part in past contest,
as close as possible to participation on time. It is
If i is odd, the robot moves to an adjacent vertex in the direction of vertex 1 ; supported only ICPC mode for virtual contests. If
you've seen these problems, a virtual contest is not
Else, i is even. You can either pay one coin (if there are some left) and then the robot moves for you - solve these problems in the archive. If you
to an adjacent vertex in the direction of vertex 1 , or not pay, and then the robot moves to an just want to solve some problem from a contest, a
virtual contest is not for you - solve this problem in
adjacent vertex chosen uniformly at random. the archive. Never use someone else's code, read
the tutorials or communicate with other person
during a virtual contest.
The process stops as soon as the robot reaches vertex 1 . Let f (v, p) be the minimum possible
expected number of steps in the process above if we spend our coins optimally. Start virtual contest
Answer q queries, in the i -th of which you have to find the value of f (vi , p i ) , modulo∗
998 244 353 . → Clone Contest to Mashup
p
∗
Formally, let M = 998 244 353 . It can be shown that the answer can be expressed as an irreducible fraction q
,
where p and q are integers and q ≢ 0 (mod M ). Output the integer equal to p ⋅ q −1 mod M . In other words, → Submit?
output such an integer x that 0 ≤ x < M and x ⋅ q ≡ p (mod M ) .
Input Language: GNU G++20 13.2 (64 bit, winlibs)
Each test contains multiple test cases. The first line contains the number of test cases t (
3 Choose
1 ≤ t ≤ 10 ). The description of the test cases follows. file:
Choose File No file chosen
3
The first line of each test case contains two integers n and q (2 ≤ n ≤ 2 ⋅ 10 ; Submit
1 ≤ q ≤ 2 ⋅ 10
3
) — the number of vertices in the tree and the number of queries.
The next n − 1 lines contain the edges of the tree, one edge per line. The i -th line contains two
→ Contest materials
integers ui and vi (1 ≤ ui , vi ≤ n; ui ≠ vi ), denoting the edge between the nodes ui and vi .
Announcement
The next q lines contain two integers vi and p i (2 ;
≤ vi ≤ n 0 ≤ p i ≤ n ).
Tutorial (en)
It's guaranteed that the given edges form a tree.
3
It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10 .
3
It is guaranteed that the sum of q over all test cases does not exceed 2 ⋅ 10 .
Output
For each test case, print q integers: the values of f (vi , p i ) modulo 998 244 353 .
Formally, let M = 998 244 353 . It can be shown that the answer can be expressed as an
p
irreducible fraction q
, where p and q are integers and q ≢ 0 (mod M) . Output the integer
equal to p ⋅ q −1 mod M . In other words, output such an integer x that 0 ≤ x < M and
x ⋅ q ≡ p (mod M) .
Example
input Copy
2
4 4
1 2
2 3
2 4
2 0
3 0
4 0
3 1
12 10
1 2
2 3
2 4
1 5
[Link] 1/3
1/23/25, 7:29 PM Problem - 2040E - Codeforces
5 6
6 7
6 8
6 9
8 10
10 11
10 12
6 0
9 0
10 0
11 0
3 1
7 1
10 1
12 1
12 2
11 12
output Copy
1
6
6
2
4
9
8
15
2
3
6
9
5
5
Note
The tree in the first test case:
In the first query, the expected value is equal to 1 , since the robot starts moving from vertex 2 to
vertex 1 in the first step and the process stops.
Let's calculate the expected value in the second query (x is the number of steps):
P (x < 2) = 0 , the distance to vertex 1 is 2 and the robot cannot reach it in fewer steps.
P (x = 2) =
1
3
, since there is only one sequence of steps leading to x = 2 . This is
3 →1 2 →0.33 1 with probability 1 ⋅ 1
.
3
P (x mod 2 = 1) = 0 , since the robot can reach vertex 1 by only taking an even number
of steps.
P (x = 4) =
2
: possible paths 3 →1 2 →0.67 [3, 4] →1 2 →0.33 1 .
9
P (x = 6) =
4
: possible paths 3 →1 2 →0.67 [3, 4] →1 2 →0.67 [3, 4] →1 2 →0.33 1 .
27
i−1
P (x = i ⋅ 2) =
2
i
in the general case.
3
∞
i−1
As a result, f (v, p) = ∑ i ⋅ 2 ⋅
2
i
= 6 .
3
i=1
The tree in the second test case:
[Link] 2/3
1/23/25, 7:29 PM Problem - 2040E - Codeforces
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jan/23/2025 11:27:50UTC+5 (i2).
Desktop version, switch to mobile version.
Privacy Policy
Supported by
[Link] 3/3