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. |
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) |
| Codeforces Round 1007 (Div. 2) Editorial |
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 |
Back to search problems