codeforces-scrape

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

2228.md (28617B)


      1 Source: https://codeforces.com/blog/entry/153619
      2 
      3 Thank you for helping Marisa, Reimu, Cirno, Sanae, Amanojaku and Momoyo!
      4 
      5 **Leave a comment!**
      6 
      7 Excellent contest
      8 
      9 Good contest
     10 
     11 Average contest
     12 
     13 Bad contest
     14 
     15 Terrible contest
     16 
     17 #### [2228A - Marisa Steals Reimu's Takeout](/contest/2228/problem/A "Codeforces Round 1098 (Div. 2)")
     18 
     19 Author: [Sanae](/profile/Sanae "International Master Sanae")
     20 
     21 Solution: [Sanae](/profile/Sanae "International Master Sanae")
     22 
     23 **Step 1**
     24 
     25 **Lemma 1.** There exists an optimal solution in which each zero is divided separately.
     26 
     27 *Proof.* Suppose in some optimal solution, a zero is grouped with other elements. Separating it into a singleton group does not decrease the total score. Hence, we can transform any optimal solution into one where all zeros are divided separately without worsening the objective. $\blacksquare$
     28 
     29 Therefore, we can restrict our attention to the subsequence consisting only of $1$s and $2$s.
     30 
     31 **Step 2**
     32 
     33 **Lemma 2.** There exists an optimal solution in which any group containing both $1$ and $2$ is exactly either $[1,2]$ or $[2,1]$.
     34 
     35 *Proof.* Consider a group that contains $1$, $2$, and possibly other elements. Splitting it into $[1,2]$ (or $[2,1]$) and the remaining part does not decrease the total score. Consequently, we can transform any optimal solution into the desired form. $\blacksquare$
     36 
     37 By Lemma 2, we can greedily extract all $[1,2]$ or $[2,1]$ pairs from the remaining sequence.
     38 
     39 **Step 3**
     40 
     41 Finally, for the leftover elements, the best strategy is clearly to take triplets $[1,1,1]$ and $[2,2,2]$ whenever possible.
     42 
     43 #### [2228B - Remilia Plays Soku](/contest/2228/problem/B "Codeforces Round 1098 (Div. 2)")
     44 
     45 Author: [Sanae](/profile/Sanae "International Master Sanae")
     46 
     47 Solution: [Sanae](/profile/Sanae "International Master Sanae")
     48 
     49 **Solution**
     50 
     51 We assume $n\geq 4$ in what follows.
     52 
     53 Let us analyze the strategies of both players. Reimu aims to get as close to Remilia as possible, while Remilia aims to get as far away from Reimu as possible. Remilia will use her moves to increase the distance without being caught, and indeed it is optimal for her to use as many moves as possible.
     54 
     55 The distance on the circle can be measured with $d=min(|x_1-x_2|,n-|x_1-x_2|)$. Once $d=1$, Remilia can increase $d$ by $1$ since the circle is large enough ($n\geq 4$). Similarly, Reimu can decrease $d$ by $1$ each turn.
     56 
     57 Therefore, we can calculate the outcome directly. The answer is the initial distance plus the extra time gained by Remilia's moves, $min(|x_1-x_2|,n-|x_1-x_2|)+k$.
     58 
     59 Note that when $n\leq 3$, the answer is always $1$, because Reimu can always catch Remilia in one step.
     60 
     61 #### [2228C1 - Cirno and Number (Easy Version)](/contest/2228/problem/C1 "Codeforces Round 1098 (Div. 2)") and [2228C2 - Cirno and Number (Hard Version)](/contest/2228/problem/C2 "Codeforces Round 1098 (Div. 2)")
     62 
     63 Author: [Sanae](/profile/Sanae "International Master Sanae"), [Sugar_fan](/profile/Sugar_fan "International Grandmaster Sugar_fan")
     64 
     65 Solution: [Sanae](/profile/Sanae "International Master Sanae"), [Sugar_fan](/profile/Sugar_fan "International Grandmaster Sugar_fan")
     66 
     67 **Solution**
     68 
     69 The case $a=b$ is trivial. We consider two cases separately: $a \gt b$ and $a \lt b$.
     70 
     71 We first discuss $a \lt b$ in what follows. Consider the longest common prefix of $a$ and $b$, scanning from the highest digit to the lowest significant digit. Let $x$ be the digit of $a$ be at that position and $y$ be the digit of $b$ be at that position. If $d_n \gt x$, choose $y$ as the smallest $d_i$ such that $d_i \gt x$. Then set the digits beneath in $b$ to $d_1$. This guarantees that $b$ is the smallest number greater than $a$ and the decimal representation of $b$ contains only digits from $d$. Otherwise, if $d_n \lt x$,we should change an earlier digit to satisfy the inequality. Note that **we can make the number of digits in $b$ more than $a$.**
     72 
     73 Similarly, we assume $a \gt b$. Consider the longest common prefix of $a$ and $b$, scanning from the highest digit to the lowest significant digit. Let $x$ be the digit of $a$ be at that position and $y$ be the digit of $b$ be at that position. If $d_1 \lt x$, choose $y$ as the largest $d_i$ such that $d_i \lt x$. Then set the digits beneath in $b$ to $d_n$. This guarantees that $b$ is the largest number smaller than $a$ and the decimal representation of $b$ contains only digits from $d$. Otherwise, if $d_1 \gt x$,we should change an earlier digit to satisfy the inequality. Note that **if $d=[1,2,3]$, then $b=0$ is invalid, because $0$ dosn't belongs to $d$.**
     74 
     75 Depending on the implementation, the time complexity can be $O(10n\log a)$, $O(10n\log^2 a)$, $O(n\log a)$ or $O(n\log^2 a)$.
     76 
     77 #### [2228D - Sanae, Cross and Color](/contest/2228/problem/D "Codeforces Round 1098 (Div. 2)")
     78 
     79 Author: [Sanae](/profile/Sanae "International Master Sanae")
     80 
     81 Solution: [Sanae](/profile/Sanae "International Master Sanae"), [fanhuaxingyu](/profile/fanhuaxingyu "Candidate Master fanhuaxingyu")
     82 
     83 **Solution 1**
     84 
     85 We can apply the principle of inclusion--exclusion to compute the answer. First, enumerate a vertical dividing line at integer coordinate $x$ from $1$ to $n$; the contribution is recalculated only when the set of points on the left side changes ~---otherwise, we skip redundant computations.
     86 
     87 For each such $x$, we then enumerate a horizontal dividing line at integer $y$ from $1$ to $n$, while carefully excluding overlapping cases to avoid double-counting. Let the y-coordinates of the points on the left side be ${y_1,y_2,\dots,y_k}$, sorted in increasing order. For consecutive y-values $y_i$ and $y_{i+1}$, all values in the form $k+0.5$ in the interval $(y_i+0.5,\;y_{i+1}-0.5)$ give the same left-side point set. Thus, the left side produces a set of y-intervals, and similarly, the right side also forms a set of y-intervals. To count all valid configurations, we need to count the number of interval-pairs (one interval from the left, one from the right) that intersect in at least one point. This can be computed efficiently using a Fenwick tree (Binary Indexed Tree) and a set data structure.
     88 
     89 The overall time complexity is $O(n\log n)$.
     90 
     91 **Solution 2**
     92 
     93 An observation is that any valid dividing line must cross at least one of the two groups determined by the smaller y-coordinate.
     94 
     95 Suppose the line crosses the group with smaller $x$ and smaller $y$. Enumerate the point whose $y$-coordinate is maximal within this group (and among those with the same maximal $y$, take the one with the larger $x$). Using appropriate pre-computation, we can efficiently determine the feasible vertical dividing position $x$.
     96 
     97 The case where the line crosses the group with larger $x$ but smaller $y$ is symmetric to the above.
     98 
     99 The overall time complexity is $O(n)$.
    100 
    101 #### [2228E1 - Amanojaku and Sequence (Easy Version)](/contest/2228/problem/E1 "Codeforces Round 1098 (Div. 2)") and [2228E2 - Amanojaku and Sequence (Hard Version)](/contest/2228/problem/E2 "Codeforces Round 1098 (Div. 2)")
    102 
    103 Author: [Sanae](/profile/Sanae "International Master Sanae")
    104 
    105 Solution: [Sanae](/profile/Sanae "International Master Sanae")
    106 
    107 Tutorial: [CirnoNine](/profile/CirnoNine "International Master CirnoNine"), [fanhuaxingyu](/profile/fanhuaxingyu "Candidate Master fanhuaxingyu")
    108 
    109 **Sanae's Solution**
    110 
    111 First, consider solving the whole array. We can first compute the total number of possible configurations of $a$ using stars and bars. Let this number be $tot$. The remaining sum to be freely distributed is $sum= m - \sum_{i} a_i[a_i\neq -1]$, and the number of undetermined positions is $cnt=\sum_{i} [a_i = -1]$. It is obvious $tot=\binom{sum+cnt-1}{cnt-1}$. We adopt the convention $\binom{-1}{-1}=1$ to simplify boundary cases.
    112 
    113 $ \begin{aligned} g(a,m)= {} & \sum_{b \text{ is valid}}\sum_{1\leq i \leq n}(\sum_{1\leq j\leq i}b_j)^2\\ = & \sum_{b \text{ is valid}}\sum_{1\leq i \leq n}\sum_{1\leq j\leq n}b_ib_j (n+1-\max(i,j))\\ = & 2\sum_{b \text{ is valid}}\sum_{1\leq i \lt j\leq n}b_ib_j (n+1-j)\\ &\quad + \sum_{b \text{ is valid}}\sum_{1\leq i \leq n}b_i^2 (n+1-i))\\ \end{aligned} $
    114 
    115 Denote $S_1=2\sum_{b \text{ is valid}}\sum_{1\leq i \lt j\leq n}b_ib_j (n+1-j)$ and $S_2=\sum_{b \text{ is valid}}\sum_{1\leq i \leq n}b_i^2 (n+1-i))$. We should compute each part individually.
    116 
    117 To do the computation, we need to first introduce some useful math conclusions. We give the $T_0,T_1,T_2$.
    118 
    119 We recall the following standard combinatorial identities: \begin{enumerate} \item If $n\geq 0$, then $\binom{n}{m}=\binom{n}{n-m}$
    120 
    121 \item For any $n,m$,then $m\binom{n}{m}=n\binom{n-1}{m-1}$
    122 
    123 \item If $n,m\geq 0$, then $n\binom{n+m}{n}=(m+1)\binom{n+m}{m+1}$ \end{enumerate}
    124 
    125 The $T_0$ is classic,while $T_1,T_2$ need some work.
    126 
    127 $ \begin{aligned} T_0(n,m) = &\sum_{x=0}^n \binom{x+m}{m}\\ = & \binom{n+m+1}{m+1} \end{aligned} $
    128 
    129 The computation of $T_1$ is straightforward.
    130 
    131 $ \begin{equation} \begin{aligned} T_1(n,m) = & \sum_{x=0}^n x\binom{x+m}{m}\\ = & \sum_{x=0}^n x\binom{x+m}{m}\\ = & \sum_{x=0}^n x\binom{x+m}{x}\\ = & \sum_{x=0}^n (m+1)\binom{x+m}{m+1}\\ = & (m+1)\binom{n+m+1}{m+2}\\ \end{aligned} \end{equation} $
    132 
    133 Similarly, we compute $T_2$:
    134 
    135 $ \begin{equation} \begin{aligned} T_2(n,m) = {}&\sum_{x=0}^n x^2\binom{x+m}{m}\\ = & \sum_{x=1}^n (m+1)x\binom{x+m}{m+1}\\ = & (m+1)\sum_{x=0}^{n-1} (x+1)\binom{x+m+1}{m+1}\\ = & (m+1)(m+2)\binom{n+m+1}{m+3}+(m+1)\binom{n+m+1}{m+2}\\ \end{aligned} \end{equation} $
    136 
    137 We now derive $T_3$:
    138 
    139 $ \begin{aligned} T_3(n,m) &= {}\sum_{x=0}^n x^3\binom{x+m}{m}\\ &= \sum_{x=1}^n (m+1)x^2\binom{x+m}{m+1}\\ &= (m+1)\sum_{x=0}^{n-1} (x+1)^2\binom{x+m+1}{m+1}\\  
    140   
    141 &= (m+1)(\sum_{x=0}^{n-1} x^2\binom{x+m+1}{m+1}+2\sum_{x=0}^{n-1} x\binom{x+m+1}{m+1}+\sum_{x=0}^{n-1} \binom{x+m+1}{m+1})\\ &= (m+1)(T_2(n-1,m+1)+2T_1(n-1,m+1)+T_0(n-1,m+1)) \\\\ &\quad \text{Note: It can be further simplified, but we can just stop here.} \end{aligned} $
    142 
    143 We first deal with $S_2$.$S_2=\sum_{1\leq i \leq n}\sum_{b \text{ is valid}}b_i^2 (n+1-i))$.If $a_i\geq 0$, $b_i=a_i$, so the formula can be written like $a_i^2(n+1-i) tot$. If $a_i=-1$,the formula can be written like
    144 
    145 $ \begin{aligned} &(n-i+1)\sum_{x=0}^{sum}x^2\binom{sum-x+cnt-2}{cnt-2}\\ =&(n-i+1)\sum_{x=0}^{sum} (sum-x)^2\binom{x+cnt-2}{cnt-2}\\ =&(n-i+1)(T_2(sum,cnt-2)-2sum\cdot T_1(sum,cnt-2)+sum^2\cdot T_0(sum,cnt-2)) \end{aligned} $
    146 
    147 Second, we cope with $S_1$.
    148 
    149 $S_1=2\sum_{b \text{ is valid}}\sum_{1\leq i \lt j\leq n}b_ib_j (n+1-j)$
    150 
    151 After selecting $i,j$, we only need to compute $\sum_{b \text{ is valid}}b_ib_j$.
    152 
    153 There are three cases:
    154 
    155 \begin{enumerate} \item $a_i\neq -1 \text{ and } a_j\neq -1$.
    156 
    157 $\sum_{b \text{ is valid}}b_ib_j=tot\cdot a_ia_j$
    158 
    159 \item $a_i\neq -1 \text{ and } a_j = -1$, $a_i\neq -1 \text{ and } a_j = -1$.
    160 
    161 It remains to consider $a_i\neq -1 \text{ and } a_j = -1$, because another case is similar.
    162 
    163 $ \begin{aligned} &\sum_{b \text{ is valid}}b_ib_j\\ =&\sum_{b_j=0}^{sum}a_ib_j\binom{sum-b_j+cnt-2}{cnt-2}\\ =&a_i\sum_{b_j=0}^{sum}(sum-b_j)\binom{b_j+cnt-2}{cnt-2}\\ =&a_i(sum\binom{sum+cnt-1}{cnt-1}-\sum_{b_j=0}^{sum}b_j\binom{b_j+cnt-2}{cnt-2})\\ =&a_i(sum\binom{sum+cnt-1}{cnt-1}-(cnt-1)\binom{sum+cnt-1}{cnt})\\ =&a_i\frac{sum\binom{sum+cnt-1}{cnt-1}}{cnt}\\ \end{aligned} $
    164 
    165 It can also be computed by the expectation of each position.
    166 
    167 \item $a_i = -1 \text{ and } a_j = -1$.
    168 
    169 It is the trickiest part of the solution. We analyze this case carefully.
    170 
    171 $ \begin{aligned} &\sum_{b \text{ is valid}}b_ib_j\\ =&\sum_{b_i=0}^{sum}\sum_{b_j=0}^{sum}[b_i+b_j\leq sum]b_ib_j\binom{sum-b_i-b_j+cnt-3}{cnt-3}\\ =&\sum_{s=b_i+b_j=0}^{sum}(\sum_{b_j=0}^{s}b_i(s-b_i))\binom{sum-s+cnt-3}{cnt-3}\\ =&\sum_{s=b_i+b_j=0}^{sum}\frac{s^3-s}{6}\binom{sum-s+cnt-3}{cnt-3}\\ =&\frac{1}{6}(\sum_{s=0}^{sum}s^3\binom{sum-s+cnt-3}{cnt-3}-\sum_{s=0}^{sum}s\binom{sum-s+cnt-3}{cnt-3})\\ =&\frac{1}{6}(\sum_{s=0}^{sum}(sum-s)^3\binom{s+cnt-3}{cnt-3}-\sum_{s=0}^{sum}(sum-s)\binom{s+cnt-3}{cnt-3})\\ =&\frac{1}{6}(\sum_{s=0}^{sum}(sum^3-3s\cdot sum^2+3s^2\cdot sum - s^3)\binom{s+cnt-3}{cnt-3}\\ &\quad -sum\cdot T_0(sum,cnt-3)+T_1(sum,cnt-3))\\ =&\frac{1}{6}(sum^3\cdot T_0(sum,cnt-3)-3sum^2\cdot T_1(sum,cnt-3)+3sum\cdot T_2(sum,cnt-3)-T_3(sum,cnt-3)\\ &\quad -sum\cdot T_0(sum,cnt-3)+T_1(sum,cnt-3))\\ \end{aligned} $
    172 
    173 It is just a constant, which is easy to compute.
    174 
    175 \end{enumerate}
    176 
    177 Then, it is time to cope with $S_1$.
    178 
    179 $S_1=2\sum_{b \text{ is valid}}\sum_{1\leq i \lt j\leq n}b_ib_j (n+1-j)$
    180 
    181 For type $1$, it suffices to compute
    182 
    183 $\sum_{1\leq i \lt j\leq n}a_ia_j[a_i\neq -1 \text{ and } a_j\neq -1](n-j+1)$
    184 
    185 .
    186 
    187 For type $2$, it suffices to compute
    188 
    189 $\sum_{1\leq i \lt j\leq n}a_i[a_i\neq -1 \text{ and } a_j = -1](n-j+1)+a_j[a_i= -1 \text{ and } a_j \neq -1](n-j+1)$
    190 
    191 .
    192 
    193 For type $3$, it suffices to compute
    194 
    195 $\sum_{1\leq i \lt j\leq n}[a_i= -1 \text{ and } a_j = -1](n-j+1)$
    196 
    197 .
    198 
    199 All required quantities can be maintained using a segment tree, and the interval queries and modifications can be processed easily. Note that $n-j+1=(n+1)-j$. So process $X \cdot(n+1)$ and $X \cdot j$ in two data structures. Implementation details are omitted for brevity; see the accompanying code.
    200 
    201 By querying on the tree, we can get the answer. And the information can also be modified efficiently.
    202 
    203 After all, we can solve the problem in the total time complexity $O(1\ 000\ 000)-O((n+q)\log n)$ and total space complexity $O(1\ 000\ 000+n)$.
    204 
    205 Note $\binom{-1}{-1}=1$ in the code.
    206 
    207 **CirnoNine's Solution**
    208 
    209 For a fixed query interval, denote it by $b_1,b_2,\ldots,b_L$.
    210 
    211 Define
    212 
    213 $A_i=\sum_{j=1}^{i} b_j[b_j\ge 0]$
    214 
    215 and
    216 
    217 $T_i=\sum_{j=1}^{i} [b_j=-1]$
    218 
    219 Here, $A_i$ is the prefix sum contributed by fixed positions, and $T_i$ is the number of free positions in the first $i$ elements.
    220 
    221 Let
    222 
    223 $S=\sum_{i:b_i\ge 0} b_i,\qquad k=\#\{i\mid b_i=-1\}$
    224 
    225 The total value that must be assigned to all free positions is
    226 
    227 $N=m-S$
    228 
    229 If $N \lt 0$, there is no valid sequence, so the answer is $0$.
    230 
    231 If $k=0$, there is only one possible sequence. The answer is $\sum_i A_i^2$ if $N=0$, and $0$ otherwise.
    232 
    233 Now assume $k \gt 0$ and $N\ge 0$.
    234 
    235 Let the values assigned to the $k$ free positions be
    236 
    237 $x_1,x_2,\ldots,x_k$
    238 
    239 where
    240 
    241 $x_1+x_2+\cdots+x_k=N,\qquad x_i\ge 0$
    242 
    243 The number of such assignments is
    244 
    245 $C=\binom{N+k-1}{k-1}$
    246 
    247 For prefix $i$, there are exactly $T_i$ free positions inside it. Therefore, the contribution of assigned values to this prefix is
    248 
    249 $X_{T_i}=x_1+x_2+\cdots+x_{T_i}$
    250 
    251 So the real prefix sum at position $i$ is
    252 
    253 $A_i+X_{T_i}$
    254 
    255 Therefore, we need to calculate
    256 
    257 $\sum_{\text{valid }x}\sum_{i=1}^{L}(A_i+X_{T_i})^2$
    258 
    259 Expanding the square gives
    260 
    261 $(A_i+X_{T_i})^2=A_i^2+2A_iX_{T_i}+X_{T_i}^2$
    262 
    263 Now we calculate these three parts separately.
    264 
    265 First, consider the $A_i^2$ part.
    266 
    267 Since $A_i$ does not depend on the assignment, every valid assignment contributes the same value. Hence this part contributes
    268 
    269 $C\sum_i A_i^2$
    270 
    271 Second, consider the $2A_iX_{T_i}$ part.
    272 
    273 By symmetry, among all weak compositions of $N$ into $k$ parts, every variable has the same total contribution. Thus
    274 
    275 $\sum_{\text{valid }x}x_j=C\cdot\frac{N}{k}$
    276 
    277 Therefore,
    278 
    279 $\sum_{\text{valid }x}X_t=C\cdot\frac{Nt}{k}$
    280 
    281 Substituting $t=T_i$, we get
    282 
    283 $\sum_{\text{valid }x}2A_iX_{T_i}=C\cdot\frac{2N}{k}A_iT_i$
    284 
    285 After summing over all $i$, this part contributes
    286 
    287 $C\cdot\frac{2N}{k}\sum_i A_iT_i$
    288 
    289 Third, consider the $X_{T_i}^2$ part.
    290 
    291 We need the second moment of
    292 
    293 $X_t=x_1+x_2+\cdots+x_t$
    294 
    295 For all weak compositions of $N$ into $k$ parts, we have
    296 
    297 $\sum_{\text{valid }x}x_p(x_p-1)=C\cdot\frac{2N(N-1)}{k(k+1)}$
    298 
    299 and for $p\ne q$,
    300 
    301 $\sum_{\text{valid }x}x_px_q=C\cdot\frac{N(N-1)}{k(k+1)}$
    302 
    303 Since
    304 
    305 $X_t^2=\sum_{p=1}^{t}x_p^2+2\sum_{1\le p \lt q\le t}x_px_q$
    306 
    307 we get
    308 
    309 $\sum_{\text{valid }x}X_t^2=C\left(\frac{N}{k}t+\frac{N(N-1)}{k(k+1)}(t^2+t)\right)$
    310 
    311 Equivalently,
    312 
    313 $\sum_{\text{valid }x}X_t^2=C\left(\left(\frac{N}{k}+\frac{N(N-1)}{k(k+1)}\right)t+\frac{N(N-1)}{k(k+1)}t^2\right)$
    314 
    315 Substituting $t=T_i$ and summing over all positions, the final formula is
    316 
    317 $g(b,m)=\binom{N+k-1}{k-1}\left(\sum_i A_i^2+\frac{2N}{k}\sum_i A_iT_i+\left(\frac{N}{k}+\frac{N(N-1)}{k(k+1)}\right)\sum_i T_i+\frac{N(N-1)}{k(k+1)}\sum_i T_i^2\right)$
    318 
    319 All divisions are done modulo $998244353$ using modular inverses.
    320 
    321 Now we explain why this can be maintained by a segment tree.
    322 
    323 For every interval, the formula only needs the following values:
    324 
    325 $S,\quad k,\quad \sum A_i,\quad \sum T_i,\quad \sum A_i^2,\quad \sum A_iT_i,\quad \sum T_i^2$
    326 
    327 Therefore, each segment tree node maintains:
    328 
    329 $len,\quad sum,\quad cnt,\quad sumA,\quad sumT,\quad sumA2,\quad sumAT,\quad sumT2$
    330 
    331 Here, $len$ is the length of the segment, $sum$ is the total fixed value in the segment, and $cnt$ is the number of $-1$ positions in the segment.
    332 
    333 The other values are:
    334 
    335 $sumA=\sum_i A_i$ $sumT=\sum_i T_i$ $sumA2=\sum_i A_i^2$ $sumAT=\sum_i A_iT_i$ $sumT2=\sum_i T_i^2$
    336 
    337 All prefix values are defined relative to the left end of the current segment.
    338 
    339 When merging two adjacent segments $L$ and $R$, every prefix inside $L$ remains unchanged.
    340 
    341 For a prefix inside $R$, the entire left segment is already before it. Therefore,
    342 
    343 $A'_i=L.sum+A_i$
    344 
    345 and
    346 
    347 $T'_i=L.cnt+T_i$
    348 
    349 So the merge formulas are:
    350 
    351 $sum=sum_L+sum_R$ $cnt=cnt_L+cnt_R$ $sumA=sumA_L+sumA_R+len_R\cdot sum_L$ $sumT=sumT_L+sumT_R+len_R\cdot cnt_L$ $sumA2=sumA2_L+sumA2_R+2sum_L\cdot sumA_R+len_R\cdot sum_L^2$ $sumAT=sumAT_L+sumAT_R+sum_L\cdot sumT_R+cnt_L\cdot sumA_R+len_R\cdot sum_L\cdot cnt_L$ $sumT2=sumT2_L+sumT2_R+2cnt_L\cdot sumT_R+len_R\cdot cnt_L^2$
    352 
    353 Thus, the maintained information is closed under concatenation, so it is suitable for a segment tree.
    354 
    355 A point update only changes one leaf, and then all nodes on the path to the root are recomputed.
    356 
    357 For a range query, we merge $O(\log n)$ segment tree nodes in left-to-right order. This gives all values required by the formula above.
    358 
    359 After precomputing factorials and inverse factorials for combinations, the total complexity is
    360 
    361 $O((n+q)\log n)$
    362 
    363 **fanhuaxingyu's Solution**
    364 
    365 ## Solution
    366 
    367 Let `sum` be the sum of all fixed values in the interval, and let `cnt` be the number of `-1`'s.
    368 
    369 If:
    370 
    371 * `sum > m`; or
    372 * `cnt = 0` and `sum ≠ m`;
    373 
    374 then no valid sequence exists, and the answer is `0`.
    375 
    376 The following discussion focuses only on valid cases.
    377 
    378 For a single query, we have a simple brute-force approach with complexity $O(nm)$.
    379 
    380 Let:
    381 
    382 * $A_i$: The sum of fixed values among the first $i$ positions;
    383 * $C_i$: The count of `-1`'s among the first $i$ positions;
    384 * $rem = m - sum$.
    385 
    386 Then:
    387 
    388 $ \begin{aligned} f(c) &=\sum_{i=1}^n(A_i+x_i)^2 \\ &=\sum_{i=1}^n \sum_{j=0}^{rem}\binom{j+C_i-1}{C_i-1} \binom{rem-j+cnt-C_i-1}{cnt-C_i-1}(A_i+j)^2 \end{aligned} $
    389 
    390 Here, $x_i$ represents the total sum distributed to the first $C_i$ unknown variables (the `-1`'s).
    391 
    392 Fixing a prefix $i$, if the unknowns in this prefix are assigned a sum of $j$, then the suffix unknowns must be assigned $rem-j$.
    393 
    394 The number of ways is given by the classic Stars and Bars method:
    395 
    396 $ W_i(j)= \binom{j+C_i-1}{C_i-1} \binom{rem-j+cnt-C_i-1}{cnt-C_i-1}. $
    397 
    398 However, this approach still has excessive complexity. We consider further optimization.
    399 
    400 $ \begin{aligned} f(c) &=\sum_{i=1}^n \sum_{j=0}^{rem}W_i(j)(A_i+j)^2 \\ &=\sum_{i=1}^nA_i^2\sum_{j=0}^{rem}W_i(j) +\sum_{i=1}^n2A_i\sum_{j=0}^{rem}jW_i(j) +\sum_{i=1}^n\sum_{j=0}^{rem}jW_i(j) +\sum_{i=1}^n\sum_{j=0}^{rem}j(j-1)W_i(j) \\ &=\binom{rem-1+cnt}{cnt-1}\sum_{i=1}^nA_i^2 +\binom{rem-1+cnt}{cnt}\sum_{i=1}^n(2A_i+1)C_i +\binom{rem-1+cnt}{cnt+1}\sum_{i=1}^nC_i(C_i+1) \end{aligned} $
    401 
    402 This recurrence uses identity transformations: - $n\binom{n+k-1}{k-1}= k\binom{n+k-1}{k}$, - $n(n-1)\binom{n+k-1}{k-1}= k(k+1)\binom{n+k-1}{k+1}$, - $\sum_{k=0}^{n} \binom{k}{a}\binom{n-k}{m-a}=\binom{n+1}{m+1}$.
    403 
    404 Thus, we obtain an $O(n)$ solution for the problem, which corresponds to the solution for **E1**.
    405 
    406 How can we optimize further?
    407 
    408 Observing the formula above, it becomes clear that if we can quickly maintain interval information such as:
    409 
    410 * $sum$,
    411 * $cnt$,
    412 * $\sum_{i=1}^nA_i^2$,
    413 * $\sum_{i=1}^nA_iC_i$,
    414 * $\sum_{i=1}^nC_i$,
    415 * $\sum_{i=1}^nC_i^2$,
    416 
    417 a Segment Tree can handle these operations within $O(\log n)$ time complexity.  
    418 Therefore, the solution for **E2** is to use a Segment Tree to optimize the recurrence formula, achieving a total time complexity of $O(M+(n+q)\log n)$.
    419 
    420 #### [2228F - Momoyo and the Network](/contest/2228/problem/F "Codeforces Round 1098 (Div. 2)")
    421 
    422 Author: [Sanae](/profile/Sanae "International Master Sanae")
    423 
    424 Solution: [Sanae](/profile/Sanae "International Master Sanae"), [juan_123](/profile/juan_123 "Grandmaster juan_123"), [SDSXC](/profile/SDSXC "Grandmaster SDSXC")
    425 
    426 **Sanae's Solution**
    427 
    428 **First Solution**
    429 
    430 We binary-search the answer $V$. The monotonicity is clear: a larger $V$ is harder to achieve, and as $k$ increases, the feasible $V$ decreases.
    431 
    432 Root the tree arbitrarily at $1$. For a node $x$, define $dp(x)$ as the maximum length (in edges) of a downward-only path starting at $x$ such that every vertex on the path satisfies: the weight of the component containing that vertex (after cutting the path) is at least $V$.
    433 
    434 During DFS, at node $x$, we have the $dp$-values of its children. We need to check whether we can form a path of length $k$ that passes through $x$ (or starts at $x$). This reduces to finding two distinct children $y_1$, $y_2$ such that $dp(y_1) + dp(y_2) + 2 \ge k$ (or a single child with $dp(y) + 1 \ge k$ if the path starts downward from $x$).
    435 
    436 Sorting the $dp$-values of the children allows an $O(\text{deg}(x)\log \text{deg}(x))$ check per node via two-pointers.
    437 
    438 The overall time complexity is: $O(n\log V\log n)$.
    439 
    440 **Second Solution**
    441 
    442 Instead of computing $dp$ by length, we can pre-compute the total weight of each subtree and sort the children of each vertex accordingly. For a candidate $V$, we can check feasibility by sorting children according to their subtree weights (or the weight of the ``outside-the-path'' component) and using a two-pointer scan to see if a $k$-edge path exists that meets the $V$ threshold everywhere.
    443 
    444 This eliminates the $\log n$ factor from sorting $dp$-values inside the binary search.
    445 
    446 The overall time complexity is: $O(n\log n+n \log V)$.
    447 
    448 **Third Solution**
    449 
    450 It's the same as the juan_123's, just for reference.
    451 
    452 Apply centroid decomposition. For a centroid $rt$, any $k$-edge path either lies entirely within one of $rt$'s subtrees (handled recursively) or passes through $rt$. In the latter case, the path consists of two legs, one in each of two different subtrees of $rt$.
    453 
    454 For each vertex $u$ in a subtree, compute the minimum component weight along the path from $u$ to $rt$ (this is the minimum of the ``remaining component weights'' for vertices on that segment). Now, choosing two vertices $u$, $v$ in different subtrees gives a path through $rt$; the overall value is the minimum of the two minima from $u$ and $v$ and the components attached to other children of $rt$.
    455 
    456 A key observation: if the largest component (by total weight) attached to $rt$ is not included in the path, it cannot be the minimum component. We only need to consider the possibility that the path touches the largest component, or handle the case where the largest component is excluded, which simplifies the check.
    457 
    458 Carefully pruning with this observation, and using appropriate data structures to query for pairs of legs whose total length is $k$, leads to an $O(n \log n)$ solution.
    459 
    460 Pruning cases where $k$ exceeds the size of the current component yields improved performance.
    461 
    462 The overall time complexity is: $O(n\log n)$.
    463 
    464 **juan_123's Solution**
    465 
    466 First, we consider how to characterize the connected components formed after deleting the edges along a path, specifically focusing on the component containing a vertex $x$ on the path.
    467 
    468 Let the root of the tree be $r$. Define $sz_x$ as the sum of weights in the subtree of $x$, $fa_x$ as the parent of $x$, and $tot$ as the sum of all $a_i$. Let LCA denote the lowest common ancestor of all points on the path. We analyze the position of $x$ on the path:
    469 
    470 1. If $x$ is an endpoint of the path but not the LCA, the edge connecting $x$ to its parent $fa_x$ is deleted, while the edges to its children remain. The size of the resulting component is
    471 
    472 $sz_x$
    473 
    474 . 2. If $x$ is neither the LCA nor an endpoint, the edges to $fa_x$ and to one specific child (say $y$) are deleted. The component size is
    475 
    476 $sz_x - sz_y$
    477 
    478 . 3. If $x$ is the LCA, then 1 or 2 edges to its children (say $y$ and $z$) are deleted. The component size is
    479 
    480 $tot - sz_y - sz_z$
    481 
    482 .
    483 
    484 We employ **Centroid Decomposition**. At each step, we fix a centroid $r_0$ as the root and consider the contribution of all paths passing through $r_0$. For any such path, the LCA is $r_0$. Let $son_{r_0}$ be the set of children of $r_0$.
    485 
    486 For contributions of type 1 and 2, we DFS the subtrees rooted at the children of $r_0$. We compute $val_{u,d}$, representing the maximum possible minimum component size if we select a path of length $d$ within the subtree of $u$ ($u \in son_{r_0}$), without yet considering the component containing the root $r_0$.
    487 
    488 Now, consider a pair $(x, y, d_0, d_1)$ where $d_0 + d_1 = k$, $x, y \in son_{r_0}$, and $x \neq y$. This represents a path with endpoints in the subtrees of $x$ and $y$ at depths $d_0$ and $d_1$, respectively. The minimum component size for this configuration is:
    489 
    490 $ \min(val_{x,d_0}, val_{y,d_1}, tot - sz_x - sz_y) $
    491 
    492 Next, we handle the term $tot - sz_x - sz_y$ associated with the root component.
    493 
    494 Note that for any $u$ and $d$,
    495 
    496 $val_{u,d} \le sz_u$
    497 
    498 . This is because $a_i > 0$, and $val$ represents splitting a subtree into parts, which cannot exceed the sum of the whole subtree.
    499 
    500 Let $v$ be the child of $r_0$ with the largest subtree size ($sz_v$). If $x \neq v$ and $y \neq v$, the size of the root's component $s = tot - sz_x - sz_y$ satisfies
    501 
    502 $s \gt sz_v \gt sz_x \ge val_{x,d}$
    503 
    504 . Since this component fully contains the large subtree of $v$, it will never be the minimum. Thus, we can ignore the root's contribution in this case and use prefix/suffix minimums to calculate the contribution efficiently.
    505 
    506 Otherwise, one endpoint lies in the subtree of $v$. We can enumerate the other endpoint's subtree, making the calculation straightforward.
    507 
    508 The total time complexity is $O(n \log n)$.
    509 
    510 A crucial detail is that during the DFS for subtree sizes, if we encounter a node that was previously a centroid root, we must add the size of the subtree blocked by that centroid to the current subtree size.
    511 
    512 **SDSXC's solution**
    513 
    514 Root the tree arbitrarily at $1$.
    515 
    516 For a node $u$, define $dp(u)$ as the maximum length (in edges) of a downward-only path starting at $u$ such that every vertex on the path satisfies: the weight of the component containing that vertex (after cutting the path) is at least $V$.
    517 
    518 Define $f(u,x)$ as the maximum $V$ satisfies: $dep(u)+dp(u)\geq x$.
    519 
    520 Define $b(u)$ as $\sum\limits_{v\in subtree(u)}a(v)$.
    521 
    522 According to the solution above, we could easily write a $O(n^2)$ brute force to calculate $f(u,x)$ and the answer. Try to optimize it by using long path decomposition.
    523 
    524 First we should calculate $f(u,x)$. The transition is: $f(u,x)=\max\limits_{fa_v=u}(\min(b(u)-b(v),f(v,x)))$ for $x \gt dep(u)$ and $f(u,x)=b(u)$ for $x=dep(u)$.
    525 
    526 The most difficult part is the $\min(b(u)-b(v),f(v,x))$. Note that, $f(v,x)\geq f(v,x+1)$, so every time we set a prefix of $f(v)$ to $b(u)-b(v)$, we use something similar to ODT to solve this. Instead of maintain $(x,val)$ to represent $f(u,x)=val$, we maintain $(l,r,val)$ to represent $f(u,x)=val$ for all $x\in [l,r]$. The other part is easy to solve.
    527 
    528 Then we should calculate the answer. We calculate the answer at the lca of the path. Assume that the lca is node $u$.
    529 
    530 If $u$ is one of the endpoint, then the answer is $\max\limits_{fa_v=u}(\min(f(v,dep(u)+k),b(1)-b(v)))$. It seems that we should binerary search for the position where $f(u,dep(u)+k)$ store. But note that $f(v,x)$ is useless while $x \gt dep(u)+k$, so we erase them. And the $f(u,dep(u)+k)$ is at the end of $f(u)$.
    531 
    532 If $u$ is not a endpoint, then the answer is $\max\limits_{fa_v=fa_w=u,x+y\geq 2dep(u)+k}(\min(f(v,x),f(w,y),b(1)-b(v)-b(w)))$. It is easy to solve if there is no $b(1)-b(v)-b(w)$.
    533 
    534 Define $son(u)$ as $v$ with the maximum $b(v)$ satisfies: v is the son of $u$. Note that $\min(f(v,x),f(w,y))\leq b(1)-b(v)-b(w)$ while neither $v$ or $w$ is equal to $son(u)$. So we use brute force while $v=son(u)$ and $w=son(u)$.
    535 
    536 The overall time complexity is: $O(n)$.
    537 
    538 [code](https://codeforces.com/contest/2228/submission/374869458)
    539 
    540 **code**
    541 
    542 [374853549](/contest/2228/submission/374853549 "Submission 374853549 by loveax")