codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2071.md (28726B)


      1 Source: https://codeforces.com/blog/entry/140115
      2 
      3 We hope you enjoyed the problems! Thank you for participating in the contest! We would love to hear your feedback in the comments.
      4 
      5 **How did you find the contest?**
      6 
      7 * Great:
      8 * Good:
      9 * Average:
     10 * Bad:
     11 * Trash:
     12 
     13 **Which problem was your favorite?**
     14 
     15 * A:
     16 * B:
     17 * C:
     18 * D1:
     19 * D2:
     20 * E:
     21 * F:
     22 
     23 **Which problem did you find the least enjoyable?**
     24 
     25 * A:
     26 * B:
     27 * C:
     28 * D1:
     29 * D2:
     30 * E:
     31 * F:
     32 
     33 [2071A - The Play Never Ends](/contest/2071/problem/A "Codeforces Round 1007 (Div. 2)")
     34 
     35 **Hints**
     36 
     37 **Hint 1**
     38 
     39 When Fofo is the spectator of the first match, what is the earliest subsequent game in which he will spectate again?
     40 
     41 **Hint 2**
     42 
     43 Suppose Sosai wins the first game. What becomes clear?
     44 
     45 **Solution**
     46 
     47 Once the winner of the first match is decided, the rest of the game is completely predictable.
     48 
     49 For example, if Hohai wins the first match which Fofo spectated, we can see that:
     50 
     51 $ {} $ $ \text{Sosai} \overset{\text{Spectator of 1st: Fofo}}{\longleftrightarrow} \text{Hohai} $ $ \text{Fofo} \overset{\text{Spectator of 2nd: Sosai}}{\longleftrightarrow} \text{Hohai} $ $ \text{Fofo} \overset{\text{Spectator of 3rd: Hohai}}{\longleftrightarrow} \text{Sosai} $ $ \text{Hohai} \overset{\text{Spectator of 4th: Fofo}}{\longleftrightarrow} \text{Sosai} $ $ \text{Hohai} \overset{\text{Spectator of 5th: Sosai}}{\longleftrightarrow} \text{Fofo} $ $ \text{Sosai} \overset{\text{Spectator of 6th: Hohai}}{\longleftrightarrow} \text{Fofo} $ $ \text{Sosai} \overset{\text{Spectator of 7th: Fofo}}{\longleftrightarrow} \text{Hohai} $
     52 
     53 No matter who wins in the second match, Hohai won't be able to continue playing in the third match (even if he wins the second match) since he has already played two times in a row. Similarly, Fofo won't be able to play in the fourth match because he has already played twice in a row, regardless of the match result.
     54 
     55 As a result, Fofo won't be able to spectate in the $k$-th match for any $k$ of the form $3x + 1$.
     56 
     57 The overall time complexity is: $O(1)$.
     58 
     59 **Code**
     60 
     61 ```
     62 #include<bits/stdc++.h>
     63 using namespace std;
     64 void solve() {
     65     int k;
     66     cin >> k;
     67     if (k % 3 == 1) {
     68         cout << "Yes\n";
     69     } else {
     70         cout << "No\n";
     71     }
     72 }
     73 int main() {
     74     ios::sync_with_stdio(0), cin.tie(0);
     75     int tt = 1;
     76     cin >> tt;
     77     while (tt--) {
     78         solve();
     79     }
     80 }
     81 ```
     82 
     83 **Rate the Problem**
     84 
     85 * Amazing problem:
     86 * Good problem:
     87 * Average problem:
     88 * Bad problem:
     89 * Didn't solve:
     90 
     91 [2071B - Perfecto](/contest/2071/problem/B "Codeforces Round 1007 (Div. 2)")
     92 
     93 **Hints**
     94 
     95 **Hint 1**
     96 
     97 Consider the identity permutation, defined by $p_i = i$. When and why does this permutation not work?
     98 
     99 **Hint 2**
    100 
    101 The smallest index $i$ where the issue occurs must satisfy the condition that $1 + \ldots + i$ is a perfect square. What is the simplest and most efficient way to resolve this issue?
    102 
    103 **Solution**
    104 
    105 The first observation is that if the sum $1 + 2 + … + n = \frac{n(n+1)}{2}$ is a perfect square, no valid perfect permutation exists.
    106 
    107 To prove that a solution always exists otherwise, start with the identity permutation $p_i = i$ and iterate through indices from $1$ to $n$. We keep on iterating as long as the prefix sum till that moment isn’t a perfect square. If the prefix sum up to index $k$ becomes a perfect square, $\frac{k(k+1)}{2} = x^2$, swap $p_k$ and $p_{k + 1}$. This changes the prefix sum to $x^2 + 1$, which is not a perfect square.
    108 
    109 To ensure this method works, we must show that $\frac{(k+1)(k+2)}{2}$ cannot also be a perfect square. Assume for contradiction that $\frac{(k+1)(k+2)}{2} = y^2$. Then:
    110 
    111 $ y^2 = x^2 + k + 1 $
    112 
    113 Since $x \gt \frac{k}{2}$ (because $x^2 = \frac{k(k+1)}{2} \gt \frac{k^2}{4}$), we have:
    114 
    115 $ {} $ $ y^2 = x^2 + k + 1 \lt x^2 + 2x + 1 = (x+1)^2 \le y^2 $
    116 
    117 which is a contradiction. Thus, $\frac{(k+1)(k+2)}{2}$ cannot be a perfect square, and the process can be repeated until all indices are processed, ensuring a valid permutation.
    118 
    119 The overall time complexity is: $O(n)$.
    120 
    121 **Code**
    122 
    123 ```
    124 #include<bits/stdc++.h>
    125 using namespace std;
    126 void solve() {
    127     auto check = [&](int k) {
    128         int j = sqrtl((int64_t)k * (k + 1) / 2);
    129         return ((int64_t)j * j != (int64_t)k * (k + 1) / 2);
    130     };
    131     int n;
    132     cin >> n;
    133     if (!check(n)) {
    134         cout << "-1\n";
    135         return;
    136     }
    137     vector<int> ans(n + 1);
    138     for (int i = 1; i <= n; i++) {
    139         ans[i] = i;
    140     }
    141     int j = 0;
    142     for (int i = 1; i <= n; i++) {
    143         while ((int64_t)j * j < (int64_t)i * (i + 1) / 2) j++;
    144         if ((int64_t)j * j == (int64_t)i * (i + 1) / 2) {
    145             swap(ans[i], ans[i + 1]);
    146         }
    147         cout << ans[i] << " ";
    148     }
    149     cout << "\n";
    150 }
    151 int main() {
    152     ios::sync_with_stdio(0), cin.tie(0);
    153     int tt = 1;
    154     cin >> tt;
    155     while (tt--) {
    156         solve();
    157     }
    158 }
    159 ```
    160 
    161 **Rate the Problem**
    162 
    163 * Amazing problem:
    164 * Good problem:
    165 * Average problem:
    166 * Bad problem:
    167 * Didn't solve:
    168 
    169 [2071C - Trapmigiano Reggiano](/contest/2071/problem/C "Codeforces Round 1007 (Div. 2)")
    170 
    171 **Hints**
    172 
    173 **Hint 1**
    174 
    175 Root the tree at vertex $\textrm{en}$. What observations can you make?
    176 
    177 **Hint 2**
    178 
    179 Can the cheese be placed at the vertices in a specific sequence that prevents the mouse from moving farther away from vertex $\textrm{en}$?
    180 
    181 **Solution**
    182 
    183 First, root the tree at vertex $\textrm{en}$ and approach it step by step. Observe that after processing all vertices at the largest depth $n−1$, the mouse’s current depth cannot exceed $n−1$. By repeating this process for the next largest depth $n−2$, the mouse’s depth will inevitably become $n−2$ or less. Continuing this way, we process vertices in descending order of depth until we reach the root, achieving the desired result.
    184 
    185 The overall time complexity is: $O(n)$.
    186 
    187 **Code**
    188 
    189 ```
    190 #include<bits/stdc++.h>
    191 using namespace std;
    192 void solve() {
    193     int n, s, e;
    194     cin >> n >> s >> e;
    195     vector adj(n + 1, vector<int> ());
    196     for (int i = 1; i < n; i++) {
    197         int u, v;
    198         cin >> u >> v;
    199         adj[u].push_back(v), adj[v].push_back(u);
    200     }
    201     vector dis(n + 1, vector<int> ());
    202     vector<int> d(n + 1);
    203     auto dfs = [&](auto &&self, int v, int par) -> void {
    204         d[v] = d[par] + 1;
    205         dis[d[v]].push_back(v);
    206         for (int u: adj[v]) {
    207             if (u == par) continue;
    208             self(self, u, v);
    209         }
    210     };
    211     dfs(dfs, e, 0);
    212     for (int i = n; i >= 1; i--) {
    213         for (int j: dis[i]) {
    214             cout << j << " ";
    215         }
    216     }
    217     cout << "\n";
    218 }
    219 int main() {
    220     ios::sync_with_stdio(0), cin.tie(0);
    221     int tt = 1;
    222     cin >> tt;
    223     while (tt--) {
    224         solve();
    225     }
    226 }
    227 ```
    228 
    229 **Rate the Problem**
    230 
    231 * Amazing problem:
    232 * Good problem:
    233 * Average problem:
    234 * Bad problem:
    235 * Didn't solve:
    236 
    237 [2071D1 - Infinite Sequence (Easy Version)](/contest/2071/problem/D1 "Codeforces Round 1007 (Div. 2)")
    238 
    239 **Hints**
    240 
    241 **Hint 1**
    242 
    243 Try to determine the connection between $a_{2m}$ and $a_{2m+1}$ for indices where $2m \gt n$.
    244 
    245 **Hint 2**
    246 
    247 Try to express $a_{2m}$ as the XOR of a short prefix of terms plus at most one extra term.
    248 
    249 **Solution**
    250 
    251 For convenience, assume $n$ is odd (if not, increment $n$ and handle the edge case separately). Start by precomputing the first $2n$ terms $a_1, a_2, \ldots, a_{2n}$. For queries with indices less than or equal to $2n$, directly return the precomputed value. For $2m \gt n$, observe the following relationship
    252 
    253 $ a_{2m} = a_1 \oplus a_2 \oplus \ldots \oplus a_m = a_{2m + 1}. $
    254 
    255 Define $p = a_1 \oplus a_2 \oplus \ldots \oplus a_n$. Notice that when $m \gt n$, we can decompose the XOR sum as:
    256 
    257 $ {} $ $ a_{2m} = a_1 \oplus a_2 \oplus \ldots \oplus a_m = a_1 \oplus a_2 \oplus \ldots \oplus a_n \oplus (a_{n + 1} \oplus a_{n + 2}) \oplus (a_{n + 3} \oplus a_{n + 4}) \oplus \ldots \oplus a_m $ $ a_{2m} = p \oplus (a_{n + 1} \oplus a_{n + 2}) \oplus (a_{n + 3} \oplus a_{n + 4}) \oplus \ldots \oplus a_m $
    258 
    259 Since $n$ is odd, the pairs $(a_{n + 1} \oplus a_{n + 2}), (a_{n + 3} \oplus a_{n + 4}), \ldots$ cancel out. This simplifies the formula to:
    260 
    261 $ {} $ $ a_{2m} = a_{2m + 1} = \begin{cases} p & \text{if } m \text{ is odd}, \\ p \oplus a_m & \text{if } m \text{ is even}. \end{cases} $
    262 
    263 As a result, we can compute $a_m$ recursively by halving $m$ until $m \le 2n$, applying the parity rule at each step.
    264 
    265 The overall time complexity is: $O(n+\log(m))$.
    266 
    267 **Code**
    268 
    269 ```
    270 #include<bits/stdc++.h>
    271 using namespace std;
    272 void solve() {
    273     int n;
    274     int64_t l, r;
    275     cin >> n >> l >> r;
    276     vector<int> a(n + 1);
    277     for (int i = 1; i <= n; i++) {
    278         cin >> a[i];
    279     }
    280     vector<int> pref(n + 1);
    281     for (int i = 1; i <= n; i++) {
    282         pref[i] = pref[i - 1] + a[i];
    283     }
    284     if (n % 2 == 0) {
    285         n++;
    286         int cur = pref[n / 2] & 1;
    287         a.push_back(cur);
    288         pref.push_back(pref.back() + cur);
    289     }
    290     for (int i = n + 1; i <= n * 2; i++) {
    291         a.push_back(pref[i / 2] & 1);
    292         pref.push_back(pref[i - 1] + a[i]);
    293     }
    294     int p = pref[n] & 1;
    295     auto get = [&](int64_t x) {
    296         int ret = 0;
    297         while (true) {
    298             if (x <= n * 2) {
    299                 ret ^= a[x];
    300                 break;
    301             }
    302             ret ^= p;
    303             if ((x / 2 - n) % 2 == 0) {
    304                 break;
    305             }
    306             x /= 2;
    307         }
    308         return ret;
    309     };
    310     cout << get(l) << "\n";
    311 }
    312 int main() {
    313     ios::sync_with_stdio(0), cin.tie(0);
    314     int tt = 1;
    315     cin >> tt;
    316     while (tt--) {
    317         solve();
    318     }
    319 }
    320 ```
    321 
    322 **Rate the Problem**
    323 
    324 * Amazing problem:
    325 * Good problem:
    326 * Average problem:
    327 * Bad problem:
    328 * Didn't solve:
    329 
    330 [2071D2 - Infinite Sequence (Hard Version)](/contest/2071/problem/D2 "Codeforces Round 1007 (Div. 2)")
    331 
    332 **Hints**
    333 
    334 **Hint 1**
    335 
    336 Generalize the recursive method for evaluating an index to handle the computation of the prefix sum.
    337 
    338 **Solution**
    339 
    340 First, check the editorial of D1.
    341 
    342 **D&C Approach**
    343 
    344 To upgrade the solution, we define a recursive function:
    345 
    346 $ \text{sum}(m) = \left( \displaystyle\sum_{\substack{i \leq m \\ i \text{ even}}} a_i,\; \displaystyle\sum_{\substack{i \leq m \\ i \text{ odd}}} a_i \right). $
    347 
    348 We precompute the even and odd prefix sums for $m \le 2n$. For $m \gt 2n$, the term $a_m$ follows:
    349 
    350 $ {} $ $ a_m = \begin{cases} p & \text{if } \lfloor \frac{m}{2} \rfloor \text{ is odd}, \\ p \oplus a_{\lfloor \frac{m}{2} \rfloor} & \text{if } \lfloor \frac{m}{2} \rfloor \text{ is even}. \end{cases} $
    351 
    352 For simplicity, assume $m \equiv 1 \pmod{4}$ (if not, keep incrementing $m$ and adjusting its contribution separately).
    353 
    354 Define
    355 
    356 $ e = \displaystyle\sum_{\substack{n \lt i \leq \lfloor \frac{m}{2} \rfloor \\ i \text{ even}}} a_i = a_{n+1} + a_{n+3} + \dots + a_{\lfloor \frac{m}{2} \rfloor} $
    357 
    358 This sum can be expressed as:
    359 
    360 $e = \text{sum}(\lfloor \frac{m}{2} \rfloor)_{\text{even}} - prefix_{\text{even}}(n). $
    361 
    362 The pairs we're interested in computing are (keep in mind that $n$ is odd):
    363 
    364 $ {} $ $ a_{2n} = a_{2n + 1} = p $ $ a_{2n + 2} = a_{2n + 3} = p \oplus a_{n + 1} $ $ a_{2n + 4} = a_{2n + 5} = p $ $ a_{2n + 6} = a_{2n + 7} = p \oplus a_{n + 3} $ $ \vdots $ $ a_{m - 3} = a_{m - 2} = p $ $ a_{m - 1} = a_{m} = p \oplus a_{\lfloor \frac{m}{2} \rfloor} $
    365 
    366 Notice that the sums of the above even and odd indices are equal, and depend on $p$:
    367 
    368 $ {} $ $ both = \begin{cases} e & \text{if } p = 0, \\ (\lfloor \frac{m}{2} \rfloor - n + 1) - e & \text{if } p = 1. \end{cases} $
    369 
    370 Thus, the final sums are:
    371 
    372 $ \text{sum}(m)_{\text{even}} = prefix_{\text{even}}(2n - 1) + both $ $ \text{sum}(m)_{\text{odd}} = prefix_{\text{odd}}(2n - 1) + both $
    373 
    374 As a result, we can compute $\text{sum}(m)$ recursively by halving $m$ until $m \le 2n$, benefitting the precomputed even and odd prefix sums at each step.
    375 
    376 The overall time complexity is: $O(n+\log(m))$.
    377 
    378 **Code**
    379 
    380 ```
    381 #include<bits/stdc++.h>
    382 using namespace std;
    383 void solve() {
    384     int n;
    385     int64_t l, r;
    386     cin >> n >> l >> r;
    387     vector<int> a(n + 1);
    388     for (int i = 1; i <= n; i++) {
    389         cin >> a[i];
    390     }
    391     vector<int> pref(n + 1);
    392     for (int i = 1; i <= n; i++) {
    393         pref[i] = pref[i - 1] + a[i];
    394     }
    395     if (n % 2 == 0) {
    396         n++;
    397         int cur = pref[n / 2] & 1;
    398         a.push_back(cur);
    399         pref.push_back(pref.back() + cur);
    400     }
    401     for (int i = n + 1; i <= n * 2; i++) {
    402         a.push_back(pref[i / 2] & 1);
    403         pref.push_back(pref[i - 1] + a[i]);
    404     }
    405     vector<int> even(n * 2 + 1);
    406     for (int i = 1; i <= n * 2; i++) {
    407         even[i] = even[i - 1] + (i & 1 ? 0 : a[i]);
    408     }
    409     int p = pref[n] & 1;
    410     auto get = [&](int64_t x) {
    411         int ret = 0;
    412         while (true) {
    413             if (x <= n * 2) {
    414                 ret ^= a[x];
    415                 break;
    416             }
    417             ret ^= p;
    418             if ((x / 2 - n) % 2 == 0) {
    419                 break;
    420             }
    421             x /= 2;
    422         }
    423         return ret;
    424     };
    425     auto sum = [&](auto&& self, int64_t m) -> pair<int64_t, int64_t> {// {sum even, sum odd}
    426         if (m <= n * 2) {
    427             return {even[m], pref[m] - even[m]};
    428         }
    429         int64_t eve = even[n * 2 - 1], odd = pref[n * 2 - 1] - eve;
    430         if (m % 2 == 0) {
    431             m += 1, odd -= get(m);
    432         }
    433         if (m / 2 % 2) {
    434             m += 1, eve -= get(m);
    435             m += 1, odd -= get(m);
    436         }
    437         auto [e, _] = self(self, m / 2);
    438         e -= even[n];
    439         int64_t c = m / 2 - n + 1, both = (p ? c - e : e);
    440         eve += both, odd += both;
    441         return {eve, odd};
    442     };
    443     int64_t ans = 0;
    444     auto [re, ro] = sum(sum, r);
    445     ans += re + ro;
    446     auto [le, lo] = sum(sum, l - 1);
    447     ans -= le + lo;
    448     cout << ans << "\n";
    449 }
    450 int main() {
    451     ios::sync_with_stdio(0), cin.tie(0);
    452     int tt = 1;
    453     cin >> tt;
    454     while (tt--) {
    455         solve();
    456     }
    457 }
    458 ```
    459 
    460 **Rate the Problem**
    461 
    462 * Amazing problem:
    463 * Good problem:
    464 * Average problem:
    465 * Bad problem:
    466 * Didn't solve:
    467 
    468 [2071E - LeaFall](/contest/2071/problem/E "Codeforces Round 1007 (Div. 2)")
    469 
    470 **Hints**
    471 
    472 **Hint 1**
    473 
    474 Think about an unordered pair $(u, v)$ where both u and v are leaves in the final forest. Consider dividing all such pairs into separate categories based on their relationship in the original tree.
    475 
    476 **Hint 2**
    477 
    478 Let the first category be the pairs that are directly connected (neighbors), and analyze under what conditions both vertices become leaves.
    479 
    480 **Hint 3**
    481 
    482 For the pairs that are not direct neighbors, focus on those that share a common neighbor. Investigate how the state (fallen or not) of their neighbors influences the possibility of both vertices becoming leaves.
    483 
    484 **Solution**
    485 
    486 Let $fall_{i} $ denote the probability that the $i$-th node falls. We partition the unordered pairs $(u,v)$ into three categories:
    487 
    488 1. $u$ and $v$ are direct neighbors.
    489 2. $u$ and $v$ share a common neighbor.
    490 3. Pairs that do not satisfy the first two conditions.
    491 
    492 Now, let us analyze the contribution of the first category to the final answer. For a pair $(u,v)$ of direct neighbors, both vertices become leaves if neither $u$ nor $v$ falls and if all of their other neighbors fall. Thus, the contribution of a specific pair $(u,v)$ is given by:
    493 
    494 $ {} $ $ contribution_1(u,v) = (1 - fall_{u}) \cdot (1 - fall_{v}) \cdot \prod_{\substack{k \text{ is a neighbor of } u \text{ or } v,\, k \neq u,\, k \neq v}} fall_{k}. $
    495 
    496 The whole contribution of the first category is:
    497 
    498 $ {} $ $\sum_{(u,v) \text{ are neighbors}} contribution_1(u,v).$
    499 
    500 For the second category, $u$ and $v$ share a neighbor, so this shared neighbor either must be the only one not falling among the neighbors of $u$ and $v$, or it must fall and exactly one of the other neighbors of both $u$ and $v$ must not fall. Additionally, both $u$ and $v$ must not fall anyway. Therefore, the contribution for a pair $(u,v)$ in the second category is given by:
    501 
    502 $ {} $ $ e_i = (\prod_{c \text{ is a neighbor of } i, \, c \neq s} fall_{c}) \cdot (\sum_{c \text{ is a neighbor of } i, \, c \neq s} \frac{1 - fall_{c}}{fall_{c}}) $ $ {} $ $ contribution_2(u,v) = (1 - fall_{u}) \cdot (1 - fall_{v}) \cdot (1 - fall_{s}) \cdot \prod_{\substack{k \text{ is a neighbor of } u \text{ or } v,\, k \neq u,\, k \neq v,\, k \neq s }} fall_{k} $ $ {} $ $ + (1 - fall_{u}) \cdot (1 - fall_{v}) \cdot (fall_{s}) \cdot e_u \cdot e_v $
    503 
    504 where $s$ is the shared neighbor of $u$ and $v$.
    505 
    506 The whole contribution of the second category is:
    507 
    508 $ {} $ $\sum_{(u,v) \text{ share a neighbor}} contribution_2(u,v).$
    509 
    510 Moving to the third category: Here, $u$ and $v$ are neither direct neighbors nor do they share any common neighbor. In this case, the events that $u$ and $v$ become leaves are completely independent.
    511 
    512 Define $leaf_{i} = (1 - fall_{i}) \cdot (\prod_{c \text{ is a neighbor of } i} fall_{c}) \cdot (\sum_{c \text{ is a neighbor of } i} \frac{1 - fall_{c}}{fall_{c}})$ as the probability that vertex $i$ becomes a leaf. Hence, for a pair $(u,v)$ in this category, the contribution is given by:
    513 
    514 $ {} $ $ contribution_3(u,v) = leaf_{u} \cdot leaf_{v}.$
    515 
    516 The whole contribution of the third category is:
    517 
    518 $ {} $ $\sum_{(u,v) \in \text{third category}} contribution_3(u,v).$
    519 
    520 The final answer is obtained by summing the contributions from all three categories. We can compute the contribution of the third category by summing $leaf_{i} \cdot leaf_{j}$ for all pairs $(i, j)$ with $i \lt j$, and then subtracting the contributions corresponding to pairs that satisfy one of the first two categories. The contribution of the second category can be computed by iterating over each node and accumulating the contributions from its neighbors (since these pairs share that node as their only common neighbor). The contribution of the first category can be computed in linear time too.
    521 
    522 The overall time complexity is $O(n \cdot \log M)$, where the $\log$ factor arises from the modular inverse computations.
    523 
    524 **Code**
    525 
    526 ```
    527 #include<bits/stdc++.h>
    528 using namespace std;
    529 const int mod = 998244353;
    530 int add(int x, int y) {
    531     return x + y - (x + y >= mod) * mod;
    532 }
    533 void add2(int &x, int y) {
    534     x += y;
    535     if (x >= mod) x -= mod;
    536 }
    537 int mul(int x, int y) {
    538     return int((int64_t)x * y % mod);
    539 }
    540 int sub(int x, int y) {
    541     return x - y + (x < y) * mod;
    542 }
    543 void sub2(int &x, int y) {
    544     x -= y;
    545     if (x < 0) x += mod;
    546 }
    547 int pwr(int x, int y) {
    548     int ret = 1;
    549     while (y) {
    550         if (y & 1) ret = mul(ret, x);
    551         x = mul(x, x);
    552         y /= 2;
    553     }
    554     return ret;
    555 }
    556 int inv(int x) {
    557     return pwr(x, mod - 2);
    558 }
    559 int norm(int64_t x) {
    560     x %= mod;
    561     if (x < 0) x += mod;
    562     return int(x);
    563 }
    564 void solve() {
    565     int n;
    566     cin >> n;
    567     vector adj(n + 1, vector<int> ());
    568     vector<int> p(n + 1);
    569     for (int i = 1; i <= n; i++) {
    570         int q;
    571         cin >> p[i] >> q;
    572         p[i] = mul(p[i], inv(q));
    573         //here, p[i] is the probability that node i will fall
    574     }
    575     for (int i = 1; i < n; i++) {
    576         int u, v;
    577         cin >> u >> v;
    578         adj[u].push_back(v), adj[v].push_back(u);
    579     }
    580     vector<int> p1(n + 1), p2(n + 1);
    581     for (int i = 1; i <= n; i++) {
    582         p1[i] = sub(1, p[i]);
    583         for (int u: adj[i]) {
    584             p1[i] = mul(p1[i], p[u]);
    585         }
    586         //p1[i] is the probability that node i won't fall, but all nodes around it will fall
    587         for (int u: adj[i]) {
    588             add2(p2[i], mul(p1[i], mul(inv(p[u]), sub(1, p[u]))));
    589         }
    590         //p2[i] is the probability that node i will be a leaf (it won't fall, all it's neighbors except one will fall)
    591     }
    592     int ans = 0, sum = 0;
    593     for (int i = 1; i <= n; i++) {
    594         add2(ans, mul(p2[i], sum));
    595         add2(sum, p2[i]);
    596     }
    597     //take all contributions of unordered pairs 
    598     for (int i = 1; i <= n; i++) {
    599         //recalculate the contribution of neighboring pairs 
    600         for (auto u: adj[i]) {
    601             if (u < i) continue;
    602             //avoid calculating the same pair probabilty twice
    603             int pi = mul(p1[i], inv(p[u]));
    604             //pi is the probability that every neighbour of i would fall except for u (not including the probability of u not falling down)
    605             int pu = mul(p1[u], inv(p[i]));
    606             //pu is the probability that every neighbour of u would fall except for i (not including the probability of i not falling down)
    607             //this case is just a tree of 2 nodes, both of them are leaves
    608             add2(ans, mul(pi, pu));
    609             //subtract the old contribution
    610             sub2(ans, mul(p2[i], p2[u]));
    611         }
    612         //recalculate the contribution of pairs with a shared neighbour which is node i (ie calculate the contribution for pairs u, v such that dis(u, v) = 2 and dis(u, i) = dis(v, i) = 1
    613         sum = 0;
    614         for (int u: adj[i]) {
    615             sub2(ans, mul(sum, p2[u]));
    616             add2(sum, p2[u]);
    617             //subtract the old contribution 
    618         }
    619         //p[i] doesn't fall
    620         sum = 0;
    621         for (int u: adj[i]) {
    622             int pu = mul(p1[u], inv(p[i]));
    623             //pu is the probability that node u is a leaf connected to node i
    624             add2(ans, mul(sum, pu));
    625             add2(sum, mul(pu, sub(1, p[i])));
    626         }
    627         //p[i] falls
    628         sum = 0;
    629         for (int u: adj[i]) {
    630             int pu = sub(p2[u], mul(p1[u], mul(inv(p[i]), sub(1, p[i]))));
    631             //pu is the probability that node u is a leaf not connected to node i
    632             add2(ans, mul(sum, pu));
    633             add2(sum, mul(pu, inv(p[i])));
    634         }
    635     }
    636     cout << ans << "\n";
    637 }
    638 int main() {
    639     ios::sync_with_stdio(0), cin.tie(0);
    640     int tt = 1;
    641     cin >> tt;
    642     while (tt--) {
    643         solve();
    644     }
    645 }
    646 ```
    647 
    648 **Rate the Problem**
    649 
    650 * Amazing problem:
    651 * Good problem:
    652 * Average problem:
    653 * Bad problem:
    654 * Didn't solve:
    655 
    656 [2071F - Towering Arrays](/contest/2071/problem/F "Codeforces Round 1007 (Div. 2)")
    657 
    658 **Hints**
    659 
    660 **Hint 1**
    661 
    662 Binary search on $p$. After fixing $p$, find the maximum $p$-towering subsequence.
    663 
    664 **Hint 2**
    665 
    666 if we denote the set of indexes that correspond to the maximum "increasing" $p$-towering subsequence on prefix $i$ as $S_i$, then for any $i \lt n$: $S_i \subseteq S_{i + 1}$.
    667 
    668 **Solution**
    669 
    670 Let's do binary search on $p$. After fixing some $p$ our goal is to find the maximum $p$-towering subsequence and check if the length of that subsequence $s$ satisfies $n - s \le k$.
    671 
    672 To find the maximum $p$-towering subsequence, for each index $i$ we will find the maximum $p$-towering subsequence such that the "left" part of that subsequence is in prefix $i$ and its right part is in suffix $i$.
    673 
    674 Let's focus only on prefixes, as the suffixes can be done similarly. So, for each prefix $i$ we want to find the maximum "increasing" $p$-towering subsequence. To do it, we will traverse the array from left to right and maintain the currently found maximum subsequence. The key idea here is that as you move from left to right you only need to add new elements to the "increasing" subsequence and never delete any (or, formally speaking, if we denote the set of indexes that correspond to maximum "increasing" $p$-towering subsequence on prefix $i$ as $S_i$, then for any $i \lt n$: $S_i \subseteq S_{i + 1}$ (the proof is left to the reader).
    675 
    676 **Elaboration**
    677 
    678 Before moving to the details of implementation, let's elaborate a bit on the previous paragraph. Consider the fifth test case from the sample; suppose the current $p = 7$; and we have just arrived at the tenth element (denoted with star $^*$). Before this position, the maximum "increasing" $p$-towering subsequence consists of the first, third, and fifth elements (denoted with underlines):
    679 
    680 $[\underline{6}, 3, \underline{8}, 5, \underline{8}, 3, 2, 1, 2, 7^*, 1]$.
    681 
    682 Now we need to check if we can increase the size of the subsequence. Since $p = 7$, then we certainly can add the tenth element with value $7$ to the subsequence. However, since we add a new number to the subsequence, two numbers become available: the second one with value $3$ and the forth one with value $5$. Thus, after processing the tenth element, the maximum "increasing" $p$-towering subsequence will look like this:
    683 
    684 $[\underline{6}, \color{red}{\underline{3}}, \underline{8}, \color{red}{\underline{5}}, \underline{8}, 3, 2, 1, 2, \color{red}{\underline{7}}^*, 1]$.
    685 
    686 So we need some way to find such "new" numbers that appear when we add some elements to the subsequence (like when the element with value $5$ becomes available from the example). To resolve this we first assign $a_i := p - a_i$ for each $i$. To find the positions that are becoming available, we can search for the rightmost non-positive element on the current prefix. Once found (suppose its index is $j$), decrease all elements on the prefix $j$ by one and assign $a_j := \infty$ (to avoid this position in the future). All these operations can be performed with the help of a segment tree.
    687 
    688 This concludes the asymptotic complexity: $O(n \log{C} \log{n})$.
    689 
    690 **Code**
    691 
    692 ```
    693 #include <bits/stdc++.h>
    694 
    695 #define len(a) (int)a.size()
    696 #define all(a) a.begin(), a.end()
    697 
    698 using namespace std;
    699 const int MAXI = 1e9 + 1e7;
    700 
    701 const int MAXN = 2e5 + 100;
    702 struct Node {
    703     int min_on_subtree = 0, push_addition = 0;
    704 };
    705 Node t[MAXN * 4];
    706 int a[MAXN], pref[MAXN], suf[MAXN];
    707 
    708 class Segtree {
    709 private:
    710     int n;
    711     void add_on_subtree(int u, int val) {
    712         t[u].push_addition += val;
    713         t[u].min_on_subtree += val;
    714     }
    715     void push(int u) {
    716         if (t[u].push_addition) {
    717             add_on_subtree(u * 2 + 1, t[u].push_addition);
    718             add_on_subtree(u * 2 + 2, t[u].push_addition);
    719             t[u].push_addition = 0;
    720         }
    721     }
    722     void recalc(int u) {
    723         t[u].min_on_subtree = min(t[u * 2 + 1].min_on_subtree, t[u * 2 + 2].min_on_subtree);
    724     }
    725     void update(int u, int l, int r, int pos, int val) {
    726         if (l == r) {
    727             t[u].min_on_subtree = val;
    728         } else {
    729             push(u);
    730             int mid = (l + r) / 2;
    731             if (pos <= mid)
    732                 update(u * 2 + 1, l, mid, pos, val);
    733             else
    734                 update(u * 2 + 2, mid + 1, r, pos, val);
    735             recalc(u);
    736         }
    737     }
    738     void add_on_segment(int u, int l, int r, int ql, int qr, int val) {
    739         if (ql <= l && r <= qr)
    740             add_on_subtree(u, val);
    741         else {
    742             push(u);
    743             int mid = (l + r) / 2;
    744             if (ql <= mid)
    745                 add_on_segment(u * 2 + 1, l, mid, ql, qr, val);
    746             if (qr > mid)
    747                 add_on_segment(u * 2 + 2, mid + 1, r, ql, qr, val);
    748             recalc(u);
    749         }
    750     }
    751     int find_prev_non_pos_put_inf(int u, int l, int r, int pos) {
    752         if (t[u].min_on_subtree > 0)
    753             return -1;
    754         if (l == r) {
    755             t[u].min_on_subtree = MAXI;
    756             return l;
    757         }
    758         push(u);
    759         int mid = (l + r) / 2, res = -1;
    760         if (pos > mid)
    761             res = find_prev_non_pos_put_inf(u * 2 + 2, mid + 1, r, pos);
    762         if (res == -1)
    763             res = find_prev_non_pos_put_inf(u * 2 + 1, l, mid, pos);
    764         recalc(u);
    765         return res;
    766     }
    767 public:
    768     explicit Segtree(int n): n(n) {
    769         fill(t, t + 4 * n, Node{MAXI, 0});
    770     };
    771 
    772     void update(int pos, int val) {
    773         update(0, 0, n - 1, pos, val);
    774     }
    775     void add_on_segment(int ql, int qr, int val) {
    776         add_on_segment(0, 0, n - 1, ql, qr, val);
    777     }
    778     int find_prev_non_pos_put_inf(int pos) {
    779         return find_prev_non_pos_put_inf(0, 0, n - 1, pos);
    780     }
    781 };
    782 
    783 void f(int n, int p, int *res) {
    784     Segtree tree(n);
    785     int cur_sz = 0;
    786     for (int i = 0; i < n; i++) {
    787         tree.update(i, p - a[i]);
    788         int pos = i;
    789         while ((pos = tree.find_prev_non_pos_put_inf(pos)) != -1) {
    790             cur_sz++;
    791             tree.add_on_segment(0, pos, -1);
    792         }
    793         res[i] = cur_sz;
    794     }
    795 }
    796 
    797 int32_t main() {
    798     ios_base::sync_with_stdio(false);
    799     cin.tie(0);
    800 #ifndef ONLINE_JUDGE
    801     freopen("input.txt", "r", stdin);
    802     freopen("output.txt", "w", stdout);
    803 #endif
    804     int testcases;
    805     cin >> testcases;
    806     while (testcases--) {
    807         int n, k;
    808         cin >> n >> k;
    809         int max_a = -1;
    810         for (int i = 0; i < n; i++) {
    811             cin >> a[i];
    812             max_a = max(max_a, a[i]);
    813         }
    814         int l = 0, r = max_a + 1;
    815         while (l + 1 < r) {
    816             int mid = (l + r) / 2;
    817             f(n, mid, pref);
    818             reverse(a, a + n);
    819             f(n, mid, suf);
    820             reverse(a, a + n);
    821             reverse(suf, suf + n);
    822             int mx = -1;
    823             for (int i = 0; i < n; i++) {
    824                 if (a[i] >= mid)
    825                     mx = max(mx, pref[i] + suf[i] - 1);
    826             }
    827             if (n - mx <= k)
    828                 l = mid;
    829             else
    830                 r = mid;
    831         }
    832         cout << l << '\n';
    833     }
    834 }
    835 ```
    836 
    837 **Rate the Problem**
    838 
    839 * Amazing problem:
    840 * Good problem:
    841 * Average problem:
    842 * Bad problem:
    843 * Didn't solve: