Codeforces Round 1007 (Div. 2)

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.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
2071 Codeforces Round 1007 (Div. 2) FINISHED False 8100 35652323 Feb. 28, 2025, 2:35 p.m.

Problems

Solved
Index
Name
Type
Tags
Community Tag
Rating
( 794 ) E LeaFall PROGRAMMING combinatorics probabilities trees

You are given a tree(^{\text{∗}}) with (n) vertices. Over time, each vertex (i) ((1 \le i \le n)) has a probability of (\frac{p_i}{q_i}) of falling. Determine the expected value of the number of unordered pairs(^{\text{†}}) of distinct vertices that become leaves(^{\text{‡}}) in the resulting forest(^{\text{§}}), modulo (998\,244\,353). Note that when vertex (v) falls, it is removed along with all edges connected to it. However, adjacent vertices remain unaffected by the fall of (v). (^{\text{∗}})A tree is a connected graph without cycles. (^{\text{†}})An unordered pair is a collection of two elements where the order in which the elements appear does not matter. For example, the unordered pair ((1, 2)) is considered the same as ((2, 1)). (^{\text{‡}})A leaf is a vertex that is connected to exactly one edge. (^{\text{§}})A forest is a graph without cycles Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains a single integer (n) ((1 \le n \le 10^5)). The (i)-th line of the following (n) lines contains two integers (p_i) and (q_i) ((1 \le p_i < q_i < 998\,244\,353)). Each of the following (n - 1) lines contains two integers (u) and (v) ((1 \le u, v \le n), (u \neq v)) — the indices of the vertices connected by an edge. It is guaranteed that the given edges form a tree. It is guaranteed that the sum of (n) over all test cases does not exceed (10^5). For each test case, output a single integer — the expected value of the number of unordered pairs of distinct vertices that become leaves in the resulting forest modulo (998\,244\,353). Formally, let (M = 998\,244\,353). It can be shown that the exact answer can be expressed as an irreducible fraction (\frac{p}{q}), where (p)

Tutorials

Codeforces Round 1007 (Div. 2) Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
308398779 Az3ar E Feb. 28, 2025, 6:50 p.m. OK C++17 (GCC 7-32) TESTS 35 312 3686400
308430592 anirudh1317 E March 1, 2025, 2:21 a.m. OK C++17 (GCC 7-32) TESTS 35 327 3686400
308416823 kitsuna E Feb. 28, 2025, 9:48 p.m. OK C++17 (GCC 7-32) TESTS 35 327 6246400
308416099 kitsuna E Feb. 28, 2025, 9:38 p.m. OK C++17 (GCC 7-32) TESTS 35 374 6144000
308378054 algoishard E Feb. 28, 2025, 4:34 p.m. OK C++17 (GCC 7-32) TESTS 35 468 8499200
308392911 ay1357 E Feb. 28, 2025, 6:02 p.m. OK C++17 (GCC 7-32) TESTS 35 687 17203200
308387491 va_adi E Feb. 28, 2025, 5:25 p.m. OK C++17 (GCC 7-32) TESTS 35 781 5222400
308442985 firewater.cryyy E March 1, 2025, 4:57 a.m. OK C++17 (GCC 7-32) TESTS 35 1546 9011200
308440574 enslaved E March 1, 2025, 4:29 a.m. OK C++20 (GCC 13-64) TESTS 35 202 2662400
308419429 turkhuu622 E Feb. 28, 2025, 10:30 p.m. OK C++20 (GCC 13-64) TESTS 35 217 4608000
308396739 leaf1415 E Feb. 28, 2025, 6:31 p.m. OK C++20 (GCC 13-64) TESTS 35 218 4812800
308379875 Fysty E Feb. 28, 2025, 4:39 p.m. OK C++20 (GCC 13-64) TESTS 35 249 6451200
308438617 YumYumYum E March 1, 2025, 4:02 a.m. OK C++20 (GCC 13-64) TESTS 35 249 8294400
308396518 PaperCloud E Feb. 28, 2025, 6:29 p.m. OK C++20 (GCC 13-64) TESTS 35 249 104652800
308378792 Badr_Masaaf E Feb. 28, 2025, 4:36 p.m. OK C++20 (GCC 13-64) TESTS 35 264 7577600
308389714 ruhittanvir14 E Feb. 28, 2025, 5:39 p.m. OK C++20 (GCC 13-64) TESTS 35 281 2355200
308389775 nifeshe E Feb. 28, 2025, 5:40 p.m. OK C++20 (GCC 13-64) TESTS 35 281 8192000
308437592 cockatooo_2025GM E March 1, 2025, 3:49 a.m. OK C++20 (GCC 13-64) TESTS 35 312 4300800
308444032 424479543 E March 1, 2025, 5:08 a.m. OK C++23 (GCC 14-64, msys2) TESTS 35 156 9932800
308445144 424479543 E March 1, 2025, 5:19 a.m. OK C++23 (GCC 14-64, msys2) TESTS 35 171 2150400
308444838 424479543 E March 1, 2025, 5:16 a.m. OK C++23 (GCC 14-64, msys2) TESTS 35 171 9932800
308405823 YuukiS E Feb. 28, 2025, 7:55 p.m. OK C++23 (GCC 14-64, msys2) TESTS 35 218 5120000
308429355 huy_pr E March 1, 2025, 2 a.m. OK C++23 (GCC 14-64, msys2) TESTS 35 233 4300800
308430094 Nachia E March 1, 2025, 2:14 a.m. OK C++23 (GCC 14-64, msys2) TESTS 35 233 8704000
308388325 hezilk E Feb. 28, 2025, 5:30 p.m. OK C++23 (GCC 14-64, msys2) TESTS 35 234 3276800
308375367 tuamitk42 E Feb. 28, 2025, 4:27 p.m. OK C++23 (GCC 14-64, msys2) TESTS 35 265 8908800
308387542 SSerxhs E Feb. 28, 2025, 5:26 p.m. OK C++23 (GCC 14-64, msys2) TESTS 35 281 39424000
308411467 Tamatem.1 E Feb. 28, 2025, 8:45 p.m. OK C++23 (GCC 14-64, msys2) TESTS 35 296 2457600
308379608 rank007 E Feb. 28, 2025, 4:38 p.m. OK PyPy 3-64 TESTS 35 1156 54374400
308381492 null_lambda E Feb. 28, 2025, 4:44 p.m. OK Rust 2021 TESTS 35 374 15052800

remove filters

Back to search problems