Solutions are presented as using the least memory and the fastest execution time. It also takes the top
10 most recent solutions from each language. If you want to limit to a specific index, click the
"Solved" button and go to that problem.
Problems
Monocarp wants to hang a garland on the Christmas tree. The Christmas tree is a tree with (n) vertices rooted at vertex (1). The distance between two vertices of the tree is the number of edges on the shortest path between them, and the depth of a vertex is the distance from it to the root. The garland consists of (n) bulbs connected by wire and numbered from (1) to (n). The length of the wire between every two adjacent bulbs is (k). The garland must be hung on the tree according to the following rules: every bulb must be placed on one of the vertices of the tree, and every vertex must have exactly one bulb on it; bulb (1) must be placed on the root of the tree; each subsequent bulb has to be placed on such a vertex that its parent vertex has a bulb on it. If there are multiple such vertices, the vertex with the largest depth is chosen. If there are still multiple options, any of them can be chosen; for each pair of subsequent bulbs, the distance between the vertices they are placed on must not exceed (k). Your task is to count the number of ways to hang the garland while following all the rules and output it modulo (998244353). Two ways are considered different if there exists at least one integer (i \in 1, n) such that the (i)-th bulb is placed on different vertices in these two ways. The first line contains a single integer (t) ((1 \le t \le 10^4)) — the number of test cases. The first line of each test case contains two integers (n) and (k) ((2 \le n \le 3 \cdot 10^5); (1 \le k < n)) — the number of vertices in the tree and the distance constraint between two consecutive bulbs. The second line contains (n-1) integers (p_2, p_3, \dots, p_n) ((1 \le p_i < i)), where (p_i) is the parent of the (i)-th vertex in the tree. Additional constraint on the input: the sum of (n) over all test cases does not exceed (3 \cdot 10^5). For each test case, output one integer |
Tutorials
Submissions
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
|
355789277 |
potato167 |
G |
Dec. 29, 2025, 5:12 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
50 |
265 |
26624000 |
|
|
|
355793819 |
potato167 |
G |
Dec. 29, 2025, 5:52 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
50 |
312 |
28364800 |
|
|
|
355887820 |
shadowDH |
G |
Dec. 30, 2025, 2:49 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
50 |
421 |
19251200 |
|
|
|
355917567 |
sumyuckk |
G |
Dec. 30, 2025, 7:14 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
50 |
515 |
20992000 |
|
|
|
355946070 |
kavyanshkrishan |
G |
Dec. 31, 2025, 5:52 a.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
50 |
515 |
53145600 |
|
|
|
355887637 |
root357 |
G |
Dec. 30, 2025, 2:47 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
50 |
531 |
76800000 |
|
|
|
355788664 |
free_time |
G |
Dec. 29, 2025, 5:07 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
50 |
546 |
72089600 |
|
|
|
355841540 |
Movazed |
G |
Dec. 30, 2025, 7:40 a.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
50 |
625 |
262041600 |
|
|
|
355816655 |
tychoelling |
G |
Dec. 29, 2025, 11:57 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
50 |
687 |
70041600 |
|
|
|
355922182 |
tristansun |
G |
Dec. 30, 2025, 8:24 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
50 |
828 |
412160000 |
|
|
|
355818116 |
magikrap |
G |
Dec. 30, 2025, 12:43 a.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
50 |
218 |
25702400 |
|
|
|
355938567 |
Nyxanee |
G |
Dec. 31, 2025, 3:35 a.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
50 |
250 |
148684800 |
|
|
|
355815402 |
Ivan_len |
G |
Dec. 29, 2025, 11:22 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
50 |
265 |
27033600 |
|
|
|
355932519 |
AkaiLemon |
G |
Dec. 31, 2025, 1:10 a.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
50 |
296 |
82329600 |
|
|
|
355915068 |
ALAov |
G |
Dec. 30, 2025, 6:45 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
50 |
312 |
86937600 |
|
|
|
355938004 |
Sanae |
G |
Dec. 31, 2025, 3:25 a.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
50 |
312 |
92876800 |
|
|
|
355818524 |
Dinprosperity |
G |
Dec. 30, 2025, 12:59 a.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
50 |
312 |
226304000 |
|
|
|
355876436 |
Misuki |
G |
Dec. 30, 2025, 1:10 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
50 |
328 |
91443200 |
|
|
|
355853727 |
xvtianze |
G |
Dec. 30, 2025, 9:36 a.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
50 |
328 |
105472000 |
|
|
|
355839735 |
rabinkarp |
G |
Dec. 30, 2025, 7:24 a.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
50 |
343 |
90521600 |
|
|
|
355922986 |
ali2005_syr |
G |
Dec. 30, 2025, 8:39 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
50 |
187 |
78131200 |
|
|
|
355924787 |
hungchi17 |
G |
Dec. 30, 2025, 9:15 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
50 |
203 |
151142400 |
|
|
|
355789826 |
potato167 |
G |
Dec. 29, 2025, 5:16 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
50 |
218 |
72601600 |
|
|
|
355825581 |
EndeavorHao |
G |
Dec. 30, 2025, 3:48 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
50 |
250 |
35430400 |
|
|
|
355792405 |
Intrinix |
G |
Dec. 29, 2025, 5:39 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
50 |
250 |
66150400 |
|
|
|
355928073 |
Marckess |
G |
Dec. 30, 2025, 10:34 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
50 |
250 |
105062400 |
|
|
|
355788905 |
toufiqhasankiron |
G |
Dec. 29, 2025, 5:09 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
50 |
265 |
34713600 |
|
|
|
355793333 |
risujiroh |
G |
Dec. 29, 2025, 5:47 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
50 |
265 |
37888000 |
|
|
|
355872208 |
Getaway_Car |
G |
Dec. 30, 2025, 12:30 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
50 |
265 |
59187200 |
|
|
|
355791920 |
kaiboy |
G |
Dec. 29, 2025, 5:34 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
50 |
265 |
66150400 |
|
|
|
355809777 |
scau_accepted |
G |
Dec. 29, 2025, 9:10 p.m. |
OK |
Go |
TESTS |
50 |
343 |
69836800 |
|
|
remove filters
Back to search problems