codeforces-scrape

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

1942.md (46601B)


      1 Source: https://codeforces.com/blog/entry/126942
      2 
      3 Thank you for participating! We put a lot of effort into this contest. Special thanks to [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") for contributing to these problems.
      4 
      5 **Rating Predictions**
      6 
      7 | Person | A | B | C1 | C2 | D | E | F | G | H |
      8 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
      9 | [oursaco](/profile/oursaco "International Master oursaco") | 800 | 1200 | 1500 | 1800 | 2200 | 2400 | 2800 | 2700 | 3400 |
     10 | [priyanshu.p](/profile/priyanshu.p "Expert priyanshu.p") | 800 | 1200 | 1300 | 1600 | 2200 |  |  |  |  |
     11 | [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") | 800 | 1200 | 1400 | 1700 | 2100 | 2300 | 2900 | 2900 | 3500 |
     12 | [cry](/profile/cry "Candidate Master cry") | 800 | 1000 | 1300 | 1700 | 2100 | 2200 | 2800 | 2900 | 3500 |
     13 | [buffering](/profile/buffering "Expert buffering") | 800 | 1000 | 1500 | 1900 | 2100 | 2200 | 2700 | 2800 | 3500 |
     14 | [JagguBandar](/profile/JagguBandar "Master JagguBandar") | 800 | 1200 | 1700 | 2000 | 1800 | 2300 |  |  |  |
     15 | [omeganot](/profile/omeganot "Master omeganot") | 900 | 1000 | 1400 | 1800 | 2200 | 2300 | 2600 |  |  |
     16 | [drdilyor](/profile/drdilyor "Master drdilyor") | 800 | 1300 | 1500 | 1800 | 2100 | 2200 |  |  |  |
     17 | [jay_jayjay](/profile/jay_jayjay "Master jay_jayjay") | 900 | 1400 | 1300 | 1600 | 1800 | 2300 | 2600 | 2800 | 3500 |
     18 | [chromate00](/profile/chromate00 "Expert chromate00") | 900 | 1300 | 1400 | 1700 | 2200 | 2400 | 2700 | 2900 | 3400 |
     19 | [maxrgby](/profile/maxrgby "Candidate Master maxrgby") | 800 | 1200 | 1300 | 1700 | 2100 |  |  |  |  |
     20 | [SunShine11](/profile/SunShine11 "Expert SunShine11") | 800 | 1300 | 1500 | 1800 | 2100 |  |  |  |  |
     21 | [MridulAhi](/profile/MridulAhi "Master MridulAhi") | 800 | 1200 | 1500 | 2000 | 1900 | 2200 | 2600 | 2800 |  |
     22 | [WAtoAC2001](/profile/WAtoAC2001 "Master WAtoAC2001") | 800 | 1300 | 1600 | 2000 | 2300 |  |  | 2800 |  |
     23 | [rainboy](/profile/rainboy "Master rainboy") |  |  |  |  | 2100 | 2400 | 2800 | 2700 | 3400 |
     24 | [Geothermal](/profile/Geothermal "Legendary Grandmaster Geothermal") | 800 | 900 | 1300 | 1700 | 1800 | 2300 | 2600 | 2800 | 3500 |
     25 | [lethan3](/profile/lethan3 "Master lethan3") | 800 | 1100 | 1500 | 1900 | 2200 |  |  |  |  |
     26 | [awesomeguy856](/profile/awesomeguy856 "Master awesomeguy856") | 800 | 1200 | 1000 | 1500 | 2100 | 2100 |  | 2400 |  |
     27 | [camc](/profile/camc "Master camc") | 800 | 1100 | 1500 | 1900 | 2100 | 2200 |  |  |  |
     28 | [rqi](/profile/rqi "International Grandmaster rqi") | 1000 | 1500 | 1600 | 1900 | 2000 | 2300 | 2700 |  |  |
     29 | [sum](/profile/sum "Master sum") |  |  |  |  | 2000 | 2200 | 2600 |  |  |
     30 
     31 |  | A | B | C1 | C2 | D | E | F | G | H |
     32 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
     33 | Average | 811 | 1189 | 1455 | 1810 | 2100 | 2273 | 2709 | 2770 | 3463 |
     34 | Actual | 800 | 1100 | 1300 | 1700 | 2100 | 2300 | 2700 | 2800 | 3500 |
     35 
     36 #### Solutions
     37 
     38 ##### [1942A - Farmer John's Challenge](/contest/1942/problem/A)
     39 
     40 Problem Credits: [buffering](/profile/buffering "Expert buffering")   
     41 Analysis: [buffering](/profile/buffering "Expert buffering")
     42 
     43 **Hint 1**
     44 
     45 Solve for $k = 1$.
     46 
     47 **Answer**
     48 
     49 $a = 1, 2, 3 \dots n$ works. Why?
     50 
     51 **Hint 2**
     52 
     53 Solve for $k = n$.
     54 
     55 **Answer**
     56 
     57 $a = 1, 1, 1 \dots 1$ works. Why?
     58 
     59 **Hint 3**
     60 
     61 What other $k$ work for a given $n$?
     62 
     63 **Answer**
     64 
     65 Only $k = 1$ and $k = n$ have possible answers.
     66 
     67 **Solution**
     68 
     69 Read the hints.
     70 
     71 For $k=1$, the construction $1,2,3\dots n$ will always work because in any other cyclic shift, $n$ will be before $1$.
     72 
     73 Now, consider what happens if we want to find an array with two or more cyclic shifts that are sorted. If we consider two of these cyclic shifts, notice they are actually shifts of each other as well.
     74 
     75 So, there should be a sorted array, and a shift of it which is also sorted. What this means is that some of the first elements in the array move to the back and stays sorted, which can **only happen if all values in the array are equal.**
     76 
     77 If the array has all equal values, this gives us our construction for $k=n$. As we have seen, for $k \gt 1$, only $k=n$ is possible. Thus, for any other $k$ not equal to $1$ or $n$, we can print $-1$.
     78 
     79 **Code (C++)**
     80 
     81 ```
     82 #include <iostream>
     83 using namespace std;
     84 int main(){
     85 	int t; cin >> t;
     86 	while(t--){
     87 		int n, k; cin >> n >> k;
     88 		if(k == 1) for(int i = 0; i < n; i++) cout << i + 1 << " ";
     89 		else if(k == n) for(int i = 0; i < n; i++) cout << 1 << " ";
     90 		else cout << -1;
     91 		cout << "\n";
     92 	}
     93 }
     94 ```
     95 
     96 ##### [1942B - Bessie and MEX](/contest/1942/problem/B)
     97 
     98 Problem Credits: [buffering](/profile/buffering "Expert buffering")   
     99 Analysis: [buffering](/profile/buffering "Expert buffering")
    100 
    101 Solution 1
    102 
    103 **Hint 1**
    104 
    105 We will construct the solution forward.
    106 
    107 **Hint 2**
    108 
    109 Separate the $a_i$'s given into negative and positive cases. What does this tell us about the $\texttt{MEX}$?
    110 
    111 **Solution**
    112 
    113 We can find $p_1, p_2, ... , p_n$ in order, looking at positive and negative cases. Note that $a_i \neq 0$ because $p_i$ would equal $\texttt{MEX}$($p_1 \dots p_i$), which can never happen.
    114 
    115 * If $a_i \gt 0$, then $\texttt{MEX}$($p_1, p_2, ... p_i$) must increase from $\texttt{MEX}$($p_1, p_2, ... p_{i-1}$), so we know $p_i$ must equal $\texttt{MEX}$($p_1, p_2, ... p_{i-1}$).
    116 * Otherwise, the $\texttt{MEX}$ stays the same, so $p_i$ is just simply $\texttt{MEX}$($p_1, p_2, ... p_{i-1}$) — $a_i$.
    117 
    118 Thus, we can just maintain the $\texttt{MEX}$ and find each $p_i$ as we go forward.
    119 
    120 **Here's more justification about specific differences leading to specific MEX changes**
    121 
    122 There are only 2 things the $\texttt{MEX}$ can do: increase or stay the same (it can never decrease since larger prefixes contain smaller ones).
    123 
    124 * In the case of a positive difference, consider what would happen if the $\texttt{MEX}$ stayed the same. Since the difference is positive, the $\texttt{MEX}$ would have to be greater than the current value, which is impossible because that value had to appear earlier on in the prefix. Since the $\texttt{MEX}$ is calculated on a permutation that can’t happen. So the $\texttt{MEX}$ has to increase.
    125 
    126 * In the case of a negative value, the $\texttt{MEX}$ has to be less than the current value. But if it increased that means the current value changed its the $\texttt{MEX}$, meaning its the $\texttt{MEX}$ is now at least (current value + 1) and it is actually greater. So it has to stay the same.
    127 
    128 Note that this is also a way to show $p$ is always unique.
    129 
    130 **Code (C++)**
    131 
    132 ```
    133 #include <bits/stdc++.h>
    134 using namespace std;
    135 
    136 void solve(){
    137 	int n; cin >> n;
    138 	vector<int> a(n);
    139 	for(int& i: a) cin >> i;
    140 	vector<int> p(n), has(n + 1);
    141 	int mex = 0;
    142 	for(int i = 0; i < n; i++){
    143 		if(a[i] >= 0){
    144 			p[i] = mex;
    145 		}
    146 		else{
    147 			p[i] = mex - a[i];
    148 		}
    149 		has[p[i]] = true;
    150 		while(has[mex]) mex++;
    151 	}
    152 	for(int i: p) cout << i << " ";
    153 	cout << "\n";
    154 }
    155 
    156 int main(){
    157 	cin.tie(0) -> sync_with_stdio(0);
    158 	int T = 1;
    159 	cin >> T;
    160 	while(T--) solve();
    161 }
    162 
    163 /*   /\_/\
    164 *   (= ._.)
    165 *   / >  \>
    166 */
    167 ```
    168 
    169 Solution 2
    170 
    171 **Hint 1**
    172 
    173 We will construct the solution backwards.
    174 
    175 **Hint 2**
    176 
    177 The $\texttt{MEX}$ is determined at the last index, since all of $0, 1 \dots n-1$ appear in $p$.
    178 
    179 **Solution**
    180 
    181 Read the hints.
    182 
    183 Since we know the $\texttt{MEX}$ of the last position is $n$, then $n - p_n = a_n$. From this equation, we can find that $p_n = n - a_n$.
    184 
    185 Now, because we know $p_n$, we can determine the $\texttt{MEX}$ of the first $n-1$ numbers. Like how we found $p_n$, we can do a similar process for finding $p_{n-1}$. Doing this for $i = n, n - 1 \dots 1$ will get us a valid answer $p$.
    186 
    187 Note that this is also a way to show $p$ is always unique.
    188 
    189 ##### [1942C1 - Bessie's Birthday Cake (Easy Version)](/contest/1942/problem/C1) and [1942C2 - Bessie's Birthday Cake (Hard Version)](/contest/1942/problem/C2)
    190 
    191 Problem Credits: [cry](/profile/cry "Candidate Master cry")   
    192 Analysis: [cry](/profile/cry "Candidate Master cry")
    193 
    194 **Solution (Easy Version)**
    195 
    196 Ignoring $n$ for now, let's just focus on the $x$ chosen vertices. Sort the $x$ vertices and connect adjacent vertices to form its own smaller polygon. By drawing out some cases or if you're familiar with triangulation ([video that proves by induction](https://www.youtube.com/watch?v=2x4ioToqe_c)), you can form $x - 2$ triangles by drawing diagonals in a polygon with $x$ vertices. If you don't know it, one possible construction that always work is fixing one vertex $v$ and drawing diagonals to every other vertex not adjacent to $v$. Now, let's consider the original $n$-sided polygon. In additional to the aforementioned construction, to close the $x$-sided polygon up: for every non-adjacent vertex in the chosen vertices based on the bigger $n$-sided polygon, draw a diagonal between them. Through this construction, we can always guarantee $x - 2$ triangles.
    197 
    198 However, this doesn't account for all triangles, as some triangles can form sides with the bigger $n$-sided polygon. These triangles occur exactly when two adjacent vertex in $x$ have exactly one vertex not in $x$ between them but part of the bigger polygon. This is because one side is from the diagonals we drew, and the other two sides form from the $n$-sided polygon.
    199 
    200 Therefore, the answer is $x - 2$ + (number of adjacent chosen vertices $2$ apart). Note that the first chosen vertex is also adjacent to last chosen vertex in $x$.
    201 
    202 **Solution (Hard Version)**
    203 
    204 Read the solution to the easy version first.
    205 
    206 We can now reduce the problem to the following: For every vertex we choose, we can make one more triangle. For every chosen vertices two apart, we can make one more triangle. Let's focus on the latter condition. To maximize the effect of our $y$ vertices, we want to prioritize vertices $v$ that satisfy the following: the vertex is not included in $x$ and there is a chosen vertex two apart. Let's denote such $v$ as good.
    207 
    208 Let vertex $a$ and $b$ $(a \lt b)$ be adjacent chosen vertices in the $x$-sided polygon. There are $g = b - a - 1$ vertices for us to choose between them. There are two cases: if $g$ is odd, then we can choose $\lfloor \frac{g}{2} \rfloor$ vertices to form $\lfloor \frac{g}{2}\rfloor + 1$ extra triangles. This is because all of the vertices we choose will be good. if $g$ is even, then we can choose $\frac{g}{2}$ vertices to make $\frac{g}{2}$ extra triangles. This is because one of the vertices we choose will not be good. This shows that it is always optimal to process smaller and odd $g$ first.
    209 
    210 After processing these adjacent gaps, if we have any leftover vertices, we can just ignore them. This is because since we have maximized the number of good vertices, even though any further vertex we place will increase the answer by $1$, it will break two good vertices which will decrease the answer by $1$.
    211 
    212 **Code (C++)**
    213 
    214 ```
    215 #include <bits/stdc++.h>
    216 using namespace std;
    217 
    218 void solve(){
    219 	int n, x, y; cin >> n >> x >> y;
    220 	int initial_y = y;
    221 	vector<int> chosen(x);
    222 	for(int& i: chosen) cin >> i;
    223 	sort(chosen.begin(), chosen.end());
    224 	int ans = x - 2;
    225 	int triangles_from_even_g = 0;
    226 	vector<int> odd_g;
    227 	auto process_gap = [&](int g) -> void{
    228 		if(g <= 1){
    229 			// already two apart
    230 			ans += g;
    231 		}
    232 		else if(g % 2 == 1){
    233 			odd_g.push_back(g / 2);
    234 		}
    235 		else{
    236 			triangles_from_even_g += g / 2;
    237 		}
    238 	};
    239 	for(int i = 0; i < x - 1; i++){
    240 		process_gap(chosen[i + 1] - chosen[i] - 1);
    241 	}
    242 	process_gap((chosen[0] + n) - chosen[x - 1] - 1);
    243 	sort(odd_g.begin(), odd_g.end());
    244 	for(int g: odd_g){
    245 		if(y >= g){
    246 			// all vertices are good, so we can make g + 1 triangles
    247 			ans += g + 1;
    248 			y -= g;
    249 		}
    250 		else{
    251 			ans += y;
    252 			y = 0;
    253 			break;
    254 		}
    255 	}
    256 	int even_triangles = min(triangles_from_even_g, y);
    257 	y -= even_triangles;
    258 	ans += even_triangles;
    259 	int used_vertices = initial_y - y;
    260 	ans += used_vertices;
    261 	cout << ans << "\n";
    262 }
    263 
    264 int main(){
    265 	cin.tie(0) -> sync_with_stdio(0);
    266 	int T = 1;
    267 	cin >> T;
    268 	while(T--) solve();
    269 }
    270 
    271 /*   /\_/\
    272 *   (= ._.)
    273 *   / >  \>
    274 */
    275 ```
    276 
    277 #### [1942D - Learning to Paint](/contest/1942/problem/D)
    278 
    279 Problem Credits: [sum](/profile/sum "Master sum")   
    280 Analysis: [sum](/profile/sum "Master sum")
    281 
    282 **Hint 1**
    283 
    284 We can solve this with dynamic programming. Let $\texttt{dp}[i]$ store a list of all $\min(k, 2^i)$ highest beauties of a painting in **non-increasing** order if you only paint cells $1,2,\ldots ,i$.
    285 
    286 **Hint 2**
    287 
    288 Transitioning boils down to finding the $k$ largest elements from $n$ **non-increasing** lists. Try to do this in $\mathcal{O}((n + k) \log n)$ time.
    289 
    290 **Solution**
    291 
    292 Let $\texttt{dp}[i]$ store a list of all $\min(k, 2^i)$ highest beauties of a painting in **non-increasing** order if you only paint cells $1,2,\ldots ,i$.
    293 
    294 Let's define **merging** two lists as creating a new list that stores the $k$ highest values from the two lists.
    295 
    296 First, let's look at a slow method of transitioning. We iterate over the left endpoint $l$ such that $l \ldots i$ is a maximal painted interval. At each $l$, we merge $\texttt{dp}[l - 2]$, with $a_{l,i}$ added to each value, into $\texttt{dp}[i]$. We also merge $\texttt{dp}[i - 1]$ into $\texttt{dp}[i]$ to handle the case in which we do not paint cell $i$. If implemented well, transitioning takes $\mathcal{O}(nk)$ time leading to an $\mathcal{O}(n^2k)$ solution which is too slow.
    297 
    298 We can speed this up. This merging process boils down to finding the $k$ largest elements from $n$ **non-increasing** lists in $\mathcal{O}((n + k) \log n)$ time. We can use a priority queue that stores ($\texttt{element}, \texttt{index}$) for each list. We can do the following $k$ times: add the top of the priority queue to our answer, advance its index, and update the priority queue accordingly. This allows us to transition in $\mathcal{O}((n + k) \log n)$ time which leads to an $\mathcal{O}((n^2 + nk) \log n)$ solution.
    299 
    300 Bonus: find an $\mathcal{O}(n^2 + k)$ solution.
    301 
    302 **Code (C++)**
    303 
    304 ```
    305 #include <bits/stdc++.h>
    306 using namespace std;
    307  
    308 void solve(){
    309     int n, k;
    310     cin >> n >> k;
    311  
    312     int A[n + 1][n + 1];
    313  
    314     for (int i = 1; i <= n; i++)
    315         for (int j = i; j <= n; j++)
    316             cin >> A[i][j];
    317     
    318     // dp[i] = Answer if we consider 1...i
    319     vector<int> dp[n + 1];
    320     dp[0] = {0};
    321  
    322     for (int i = 1; i <= n; i++){
    323         priority_queue<array<int, 3>> pq;
    324  
    325         // Don't create an interval
    326         pq.push({dp[i - 1][0], i - 1, 0});
    327  
    328         // Create interval j+2...i (transition from j)
    329         for (int j = i - 2; j >= -1; j--){
    330             pq.push({(j < 0 ? 0 : dp[j][0]) + A[j + 2][i], j, 0});
    331         }
    332  
    333         while (pq.size() and dp[i].size() < k){
    334             auto [val, j, num] = pq.top(); pq.pop();
    335             dp[i].push_back(val);
    336             
    337             if (j < 0 or num + 1 >= dp[j].size())
    338                 continue;
    339             
    340             // Don't create interval
    341             if (j == i - 1)
    342                 pq.push({dp[i - 1][num + 1], i - 1, num + 1});
    343             
    344             // Create interval j+2...i (transition from j)
    345             else 
    346                 pq.push({dp[j][num + 1] + A[j + 2][i], j, num + 1});
    347         }
    348     }
    349     for (int i : dp[n])
    350         cout << i << " ";
    351     cout << "\n";
    352 }
    353  
    354 int main(){
    355     ios_base::sync_with_stdio(0); cin.tie(0); 
    356     int tc; 
    357     cin >> tc;
    358  
    359     while (tc--) 
    360         solve();
    361 }
    362 ```
    363 
    364 #### [1942E - Farm Game](/contest/1942/problem/E)
    365 
    366 Problem Credits: [cry](/profile/cry "Candidate Master cry")   
    367 Analysis: [sum](/profile/sum "Master sum")
    368 
    369 **Hint 1**
    370 
    371 Think about the gaps between $(a_1,b_1), (a_2,b_2), ... ,(a_n,b_n)$. Let the gaps be $g_1,g_2,...,g_n$. What effect do the moves have on the gaps?
    372 
    373 **Hint 2**
    374 
    375 WLOG let the first cow be FJ's cow. FN wins if all $g_i$ are even. Otherwise FJ wins. Note that the game will always end.
    376 
    377 **Hint 3**
    378 
    379 Try to count the number of ways FN wins. We can iterate over the sum of $g_i$ and use stars and bars as well as other counting techniques.
    380 
    381 **Solution**
    382 
    383 Consider the gaps between $(a_1,b_1), (a_2,b_2), ... ,(a_n,b_n)$. In the example below, '$\texttt{a}$' represents FJ's cow, '$\texttt{b}$' represents FN's cow, and '$\texttt{.}$' represents an empty space. The gaps are $[2,3]$.
    384 
    385 $\texttt{|.a..b....a...b.|}$
    386 
    387 Consider the gaps $g_1,g_2,...,g_n$. When a farmer moves, they choose some non-empty subset of non-zero $g_i$ and add or subtract $1$ from every element in the subset (so long such move is possible). The game ends when some farmer cannot move (which implies that all $g_i$ must be $0$ when the game ends).
    388 
    389 WLOG let the first cow be FJ's cow. The winner of the game is determined as follows:
    390 
    391 1) If all $g_i$ are even, then FN wins. If FJ pushes the cows corresponding to gaps $i_1, i_2, \ldots, i_k$ some direction in a move, then $g_{i_1}, g_{i_2}, \ldots g_{i_k}$ will change by $1$ and become odd. FN can then push the cows corresponding to gaps $i_1, i_2, \ldots, i_k$ **left** so that $g_{i_1}, g_{i_2}, \ldots g_{i_k}$ will become even again. Therefore, all $g_i$ will be even when it's FJ's turn and at least one $g_i$ will be odd when it's FN's turn. Since the game ends when all $g_i$ are $0$ (which is even), then FJ will lose. **Note that the game will always end.** This is since the sum of positions of FN's cows will always be decreasing since FN will always push some cow left.
    392 
    393 2) Otherwise, FJ wins since he can subtract $1$ to all odd $g_i$ in his first move to make all elements even. Then it's FN's turn and all $g_i$ are even so by the reasoning above, FJ wins.
    394 
    395 Let's use complementary counting and determine the number of ways **FN** wins (which is when all $g_i$ are even). We can iterate over the sum, $s$ ($s$ is even), of all $g_i$. At each $s$, we can use stars and bars to find how many such $g_1,g_2,...,g_n$ (all $g_i$ are even) sum to $s$. Specifically, the number of ways are $\frac{s}{2} + n - 1 \choose n - 1$. The number of ways to place the cows in the available positions given the gaps will be $2 \cdot {l - s - n \choose n}$. We multiply by $2$ since we can alternate starting with either FJ's cow or FN's cow.
    396 
    397 Finally, we subtract this result from the total number of configurations, $2 \cdot {l \choose 2 \cdot n}$, to get the number of ways FJ wins. This runs in $\mathcal{O}(l)$ time.
    398 
    399 **Code (C++)**
    400 
    401 ```
    402 #include <bits/stdc++.h>
    403 using namespace std;
    404 
    405 #define ll long long
    406 
    407 const int MAX = 2e6 + 5, MOD = 998244353;
    408 
    409 ll fact[MAX], ifact[MAX];
    410 
    411 ll bpow(ll a, int p){
    412     ll ans = 1;
    413 
    414     for (;p; p /= 2, a = (a * a) % MOD) 
    415         if (p & 1) 
    416             ans = (ans * a) % MOD;
    417 
    418     return ans;
    419 }
    420 ll ncr(int n, int r){
    421     if (n < 0)
    422         return 0;
    423     if (r > n)
    424         return 0;
    425 
    426     return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
    427 }
    428 void solve(){
    429     int l, n;
    430     cin >> l >> n;
    431  
    432     ll all_even = 0;
    433  
    434     for (int s = 0; s <= l; s += 2){
    435         all_even += 2 * ncr(s / 2 + n - 1, n - 1) % MOD * ncr(l - s - n, n) % MOD;
    436         all_even %= MOD;
    437     }
    438     cout << (2 * ncr(l, 2 * n) % MOD - all_even + MOD) % MOD << "\n";
    439 }
    440 
    441 int main(){
    442     ios_base::sync_with_stdio(0); cin.tie(0);
    443     
    444     for (int i = 0; i < MAX; i++)
    445         fact[i] = !i ? 1 : fact[i - 1] * i % MOD;
    446     
    447     for (int i = MAX - 1; i >= 0; i--)
    448         ifact[i] = (i == MAX - 1) ? bpow(fact[MAX - 1], MOD - 2) : ifact[i + 1] * (i + 1) % MOD;
    449 
    450     int tc;
    451     cin >> tc;
    452 
    453     while (tc--)
    454         solve();
    455 }
    456 ```
    457 
    458 #### [1942F - Farmer John's Favorite Function](/contest/1942/problem/F)
    459 
    460 Problem Credits: [sum](/profile/sum "Master sum")   
    461 Analysis: [sum](/profile/sum "Master sum")
    462 
    463 **Hint 1**
    464 
    465 Consider the case where all $f(i)$ are integers. Decreasing **any** $a_i$ will decrease $\lfloor f(n) \rfloor$. So solutions that iterate over the last few elements will not work.
    466 
    467 **Hint 2**
    468 
    469 If $n \ge 6$, changing $a_1$ will only affect $\lfloor f(n) \rfloor$ by at most $1$.
    470 
    471 **Hint 3**
    472 
    473 We can take the floor each time we square root. Specifically, we can define $f$ as:
    474 
    475 * $f(1) = \lfloor \sqrt{a_1} \rfloor$
    476 * For all $i \gt 1$, $f(i) = \lfloor \sqrt{f(i-1)+a_i} \rfloor$
    477 
    478 This allows us to work with integers.
    479 
    480 **Hint 4**
    481 
    482 We can divide our array into blocks of size $b \ge 6$ (note that the value of $b$ depends on the solution). How can we use hint $2$? What should we store for each block?
    483 
    484 **Solution**
    485 
    486 Let's first look at the impact of earlier numbers on the final result. Earlier numbers can still influence $\lfloor f(n) \rfloor$ when $n$ is large. Suppose that all $f(i)$ are integers. Then decreasing **any** $a_i$ will decrease $\lfloor f(n) \rfloor$.
    487 
    488 However, it is clear that the impact of earlier number on $\lfloor f(n) \rfloor$ is still extremely small. A key observation is that when $n \ge 6$, changing $a_1$ will only affect $\lfloor f(n) \rfloor$ by at most $1$.
    489 
    490 Another observation is that we can take the floor each time we square root. Specifically, we can define $f$ as:
    491 
    492 * $f(1) = \lfloor \sqrt{a_1} \rfloor$
    493 * For all $i \gt 1$, $f(i) = \lfloor \sqrt{f(i-1)+a_i} \rfloor$
    494 
    495 This allows us to work with integers. From here on, we work with this new definition of $f$.
    496 
    497 Let's divide our array into blocks of size $b=6$. We can append zeroes to the front of the array to make $n$ a multiple of $b$.
    498 
    499 Consider some block representing range $[l,r]$. Let's consider the subarray $a_l,a_{l+1},\ldots ,a_r$. Let $v$ be the value of $f(r)$ if we let $f(l - 1)=0$. Using our first observation, we know that $f(r)$ will be either $v$ or $v+1$ depending on $f(l - 1)$. So let's find the smallest value $c$ such that if $f(l - 1)=c$, then $f(r)=v+1$. This can be done by iterating over the elements of the block backwards.
    500 
    501 For each block, we store its corresponding ($v,c$). We can build a segment tree over the blocks for an $\mathcal{O}((n + q) \log n)$ solution.
    502 
    503 Alternatively, we can do square root decomposition by having $b=\sqrt n$ which leads to an $\mathcal{O}(n + q \sqrt n)$ solution (in practice, we should set $b$ to something small like $100$).
    504 
    505 **Code (C++)**
    506 
    507 **Segment Tree**
    508 
    509 ```
    510 #include <bits/stdc++.h>
    511 using namespace std;
    512 
    513 #define ll long long
    514 #define pll pair<ll, ll>
    515 
    516 const int B = 6, MAX = 2e5 + B + 5;
    517 
    518 int n, q, offset, numBlocks; ll A[MAX]; pll seg[MAX];
    519 
    520 pll comb(pll a, pll b){
    521     auto [vl, cl] = a;
    522     auto [vr, cr] = b;
    523 
    524     // Not defined
    525     if (vl == -1)
    526         return b;
    527     if (vr == -1)
    528         return a;
    529 
    530     // Doesn't cross cutoff
    531     if (vl < cr - 1)
    532         return {vr, (ll)2e18};
    533     if (vl >= cr)
    534         return {vr + 1, (ll)2e18};
    535     
    536     // If vl == cr - 1
    537     return {vr, cl};
    538 }
    539 void updSeg(int i, pll v){
    540     seg[i += numBlocks] = v;
    541 
    542     for (i /= 2; i > 0; i /= 2) 
    543         seg[i] = comb(seg[i * 2], seg[i * 2 + 1]);
    544 }
    545 ll qry(int l = 0, int r = numBlocks - 1){ 
    546     pll retL = {-1, -1};
    547     pll retR = {-1, -1};
    548 
    549     for (l += numBlocks, r += numBlocks; l <= r; r /= 2, l /= 2){
    550         if (l % 2 == 1) 
    551             retL = comb(retL, seg[l++]);
    552         if (r % 2 == 0) 
    553             retR = comb(seg[r--], retR);
    554     }
    555     return comb(retL, retR).first;
    556 }
    557 void updBlock(int blk){
    558     int l = blk * B;
    559     int r = l + B - 1;
    560 
    561     ll val = 0;
    562     for (int i = l; i <= r; i++)
    563         val = floor(sqrtl((long double)val + A[i]));
    564     
    565     ll req = val + 1;
    566     for (int i = r; i >= l; i--){
    567         if (req > 2e9){
    568             updSeg(blk, {val, (ll)2e18});
    569             return;
    570         }
    571         req = req * req - A[i];
    572     }
    573     updSeg(blk, {val, req});
    574 }
    575 
    576 int main(){
    577     ios_base::sync_with_stdio(0); cin.tie(0); 
    578     cin >> n >> q;
    579 
    580     offset = (B - n % B) % B;
    581     n += offset;
    582     numBlocks = n / B;
    583 
    584     for (int i = offset; i < n; i++)
    585         cin >> A[i];
    586     
    587     for (int b = 0; b < numBlocks; b++)
    588         updBlock(b);
    589 
    590     while (q--){
    591         ll k, x;
    592         cin >> k >> x;
    593         k--; 
    594         k += offset;
    595 
    596         A[k] = x;
    597         updBlock(k / B);
    598 
    599         cout << qry() << "\n";
    600     }
    601 }
    602 ```
    603 
    604 **Square Root Decomposition**
    605 
    606 ```
    607 #include <bits/stdc++.h>
    608 using namespace std;
    609 
    610 #define ll long long
    611 
    612 const int B = 100, MAX = 2e5 + B + 5;
    613 
    614 int n, q, offset, numBlocks; ll A[MAX], val[MAX], cut[MAX];
    615 
    616 void buildBlock(int blk){
    617     int l = blk * B;
    618     int r = l + B - 1;
    619 
    620     ll cur = 0;
    621 
    622     for (int i = l; i <= r; i++)
    623         cur = floor(sqrtl((long double)cur + A[i]));
    624     
    625     val[blk] = cur;
    626 
    627     ll req = cur + 1;
    628 
    629     for (int i = r; i >= l; i--){
    630         if (req > 2e9){
    631             cut[blk] = 2e18;
    632             return;
    633         }
    634         req = req * req - A[i];
    635     }
    636     cut[blk] = req;
    637 }
    638 ll qry(){
    639     ll cur = 0;
    640 
    641     for (int b = 0; b < numBlocks; b++)
    642         cur = (cur >= cut[b]) ? val[b] + 1 : val[b];
    643     
    644     return cur;
    645 }
    646 
    647 int main(){
    648     ios_base::sync_with_stdio(0); cin.tie(0); 
    649     cin >> n >> q;
    650 
    651     offset = (B - n % B) % B;
    652     n += offset;
    653     numBlocks = n / B;
    654 
    655     for (int i = offset; i < n; i++)
    656         cin >> A[i];
    657     
    658     for (int b = 0; b < numBlocks; b++)
    659         buildBlock(b);
    660 
    661     while (q--){
    662         ll k, x;
    663         cin >> k >> x;
    664         k--; 
    665         k += offset;
    666 
    667         A[k] = x;
    668         buildBlock(k / B);
    669 
    670         cout << qry() << "\n";
    671     }
    672 }
    673 ```
    674 
    675 #### [1942G - Bessie and Cards](/contest/1942/problem/G)
    676 
    677 Problem Credits: [smax](/profile/smax "Grandmaster smax")   
    678 Analysis: [smax](/profile/smax "Grandmaster smax")
    679 
    680 **Hint 1**
    681 
    682 "Draw $1$" cards do not matter because we can immediately play them when we draw them.
    683 
    684 **Hint 2**
    685 
    686 Treat "draw $2$" as $+1$ and "draw $0$" as $-1$. We start with a balance of $+5$. We draw all the cards up to the first prefix where the balance dips to $0$. We are interested in the number of ways where the special cards lie in this prefix.
    687 
    688 **Solution**
    689 
    690 Read the hints.
    691 
    692 Treat the special cards as "draw $0$" cards and multiply by the appropriate binomial coefficient at the end. Also treat cards of the same type as indistinguishable and multiply by the appropriate factorials at the end.
    693 
    694 Enumerate the length of the prefix where the balance first hits $0$. This dictates how many $+1$ and $-1$ we have. Now we want to count the number of ways of arranging $+1$ and $-1$ such that the balance never dips to $0$, assuming we start with $+5$.
    695 
    696 To solve this subproblem, we can draw inspiration from the [path counting interpretation](https://en.wikipedia.org/wiki/Catalan_number#Second_proof) for counting balanced bracket sequences. We have $n$ open and $n$ close brackets and want to count the number of balanced bracket sequences starting with `((((` (note that there are only $4$ instead of $5$ open brackets to shift from all balances being strictly positive to all balances being non-negative). The number of sequences ignoring the balance constraint is $\binom{2n-4}{n}$. Any bracket sequence where some balance dips negative corresponds to a path that walks above the line $y = x$. For those paths, we reflect over the line $y = x + 1$ at the first point where it steps over the line. So there is a bijection between these paths and paths that reach the point $(n-1,n+1)$, of which there are $\binom{2n-4}{n+1}$. So the total number of ways is $\binom{2n-4}{n} - \binom{2n-4}{n+1}$.
    697 
    698 Our final answer is summing up the number of ways over all prefix lengths. Make sure to handle the case where you draw the entire deck correctly. The complexity is $\mathcal O(\min(a,c))$.
    699 
    700 **Code (C++)**
    701 
    702 #### [1942H - Farmer John's Favorite Intern](/contest/1942/problem/H)
    703 
    704 Problem Credits: [oursaco](/profile/oursaco "International Master oursaco")   
    705 Analysis: [oursaco](/profile/oursaco "International Master oursaco") / [rainboy](/profile/rainboy "Candidate Master rainboy")
    706 
    707 **Solution 1**
    708 
    709 Model this as a flow problem where growth events are an input of some flow to a node and harvest events and the necessary amount of fruits are an output of flow to the sink. We will define the $a_i$ edge to be the input edge of every node, $b_i$ to be the output edge for necessary fruits, and $c_i$ to be the output edge for growth events. The connections for each individual node will look like:
    710 
    711 $(\text{source}, a_i, \text{# of growth events})$
    712 
    713 $(a_i, \text{temporary node}, \text{INF})$
    714 
    715 $(\text{temporary node}, b_i, \text{INF})$
    716 
    717 $(\text{temporary node}, c_i, \text{INF})$
    718 
    719 $(b_i, \text{sink}, \text{# of required peaches})$
    720 
    721 $(c_i, \text{sink}, \text{# of harvest events})$
    722 
    723 To simulate growth events affecting the subtree, every temporary node has infinite capacity directed edges down to the temporary nodes of its children. To simulate growth events affecting the parent, every temporary node has an infinite capacity directed edge to its parent's $b_i$. To simulate harvest events affecting subtree, every node has infinite capacity directed edges to all its ancestors' $c_i$ nodes. Lets try to find the min cut of the graph. If we don't put cut some node's $a_i$, then we must cut both $b_i$ and $c_i$ for all of its descendants. If we don't cut some node's $a_i$, then we also must cut $c_i$ for all its ancestors and $b_i$ for its parent. Thus, we can model a $dp[i][0/1/2]$ to know if we are currently cutting the a_i input edge, cutting the b_i and c_i output edge, or cutting the a_i edge but there is some node in the subtree where we did not cut the a_i edge, in which case we need to cut the c_i edge as well. Transitions look like:
    724 
    725 $dp[i][0] = a_i + \sum_j dp[j][0]$
    726 
    727 $dp[i][1] = b_i + c_i + \sum_j dp[j][1]$
    728 
    729 $dp[i][2] = a_i + c_i + \min(\sum_j \min(dp[j][0], dp[j][2]), b_i + \sum_j \min(dp[j][0], dp[j][1], dp[j][2]))$ where at least one child is a $dp[j][2]$ or $dp[j][1]$
    730 
    731 $dp[i][2]$ can be rewritten as:
    732 
    733 $dp[i][2] = a_i + c_i + \min(\min(dp[j][2] - \min(dp[j][0], dp[j][2])) + \sum_j \min(dp[j][0], dp[j][2]),$ $\min(dp[j][1] - \min(dp[j][0], dp[j][1], dp[j][2])) + b_i + \sum_j \min(dp[j][0], dp[j][1], dp[j][2])))$
    734 
    735 Use dynamic dp by representing dp transitions as a matrix where all the light children dp values are known and the heavy child dp values are variable. Then, we can accelerate each chain in the heavy light decomposition of the tree. To get the matrix representation of each transition to the heavy child, there are 5 cases when considering a $dp[j][0/1/2]$ -> $dp[j][2]$ transiton where $dp[j][0]$ is the min, $dp[j][1]$ is the min, and $dp[j][2]$ is the min, $dp[j][2] - \min(dp[j][0], dp[j][2])$ is the optimal added value, or $dp[j][0] - min(dp[j][0], dp[j][1], dp[j][2])$, is the optimal added value. For each cell in the matrix, put the min of the $5$ cases.
    736 
    737 Since you will only ever change hld chains $\log n$ times, the total complexity will be $n \log^2 n \cdot 3^3$. If we use balanced hld or other $n \log n$ hld techniques, then the complexity becomes $n \log^2 n$. Both solutions should pass under the given constraints.
    738 
    739 **Code (C++)**
    740 
    741 ```
    742     #ifndef LOCAL
    743     #pragma GCC optimize("O3,unroll-loops")
    744     #pragma GCC target("avx,avx2,fma")
    745     #pragma GCC target("sse4,popcnt,abm,mmx,tune=native")
    746     #endif
    747     #include <bits/stdc++.h>
    748     #include <ext/pb_ds/assoc_container.hpp>
    749     #include <ext/pb_ds/tree_policy.hpp>
    750     using namespace __gnu_pbds;
    751     using namespace std;
    752     
    753     #define pb push_back
    754     #define ff first
    755     #define ss second
    756     
    757     typedef long long ll;
    758     typedef long double ld;
    759     typedef pair<int, int> pii;
    760     typedef pair<ll, ll> pll;
    761     typedef pair<ld, ld> pld;
    762     
    763     const int INF = 1e9;
    764     const ll LLINF = 1e18;
    765     const int MOD = 1e9 + 7;
    766     
    767     template<class K> using sset =  tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
    768     
    769     inline ll ceil0(ll a, ll b) {
    770         return a / b + ((a ^ b) > 0 && a % b);
    771     }
    772     
    773     void setIO() {
    774         ios_base::sync_with_stdio(0); cin.tie(0);
    775     }
    776     
    777     struct Matrix {
    778     
    779         array<array<ll, 3>, 3> mat;
    780     
    781         array<ll, 3> &operator[](int x){
    782             return mat[x];
    783         }
    784     
    785         const array<ll, 3> &operator[](int x) const {
    786             return mat[x];
    787         }
    788     
    789         Matrix(){
    790             for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) mat[i][j] = 0;
    791         }
    792     
    793         Matrix operator*(const Matrix &x){
    794             Matrix ret;
    795             for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) ret[i][j] = LLINF;
    796             for(int i = 0; i < 3; i++){
    797                 for(int k = 0; k < 3; k++){
    798                     for(int j = 0; j < 3; j++){
    799                         ret[i][j] = min(ret[i][j], mat[i][k] + x[k][j]);
    800                     }
    801                 }
    802             }
    803             return ret;
    804         }
    805     
    806         Matrix &operator*=(const Matrix &x){
    807             (*this) = (*this) * x;
    808             return *this;
    809         }
    810     };
    811     
    812     struct fastset {
    813     
    814         priority_queue<ll, vector<ll>, greater<ll>> q, rem;
    815     
    816         void insert(ll x){
    817             q.push(x);
    818         }
    819     
    820         void erase(ll x){
    821             rem.push(x);
    822         }
    823     
    824         ll query(){
    825             while(rem.size() && q.top() == rem.top()){
    826                 rem.pop();
    827                 q.pop();
    828             }
    829             return q.top();
    830         }
    831     
    832         void clear(){
    833             while(q.size()) q.pop();
    834             while(rem.size()) rem.pop();
    835         }
    836     };
    837     
    838     vector<int> g[500005];
    839     int sub[500005];
    840     int head[500005];
    841     int par[500005];
    842     int tim = 0;
    843     vector<int> chain[500005];
    844     int weight[500005];
    845     
    846     void dfs1(int x){
    847         sub[x] = 1;
    848         for(int &i : g[x]){
    849             dfs1(i);
    850             sub[x] += sub[i];
    851             if(sub[i] > sub[g[x][0]]) swap(i, g[x][0]);
    852         }
    853     }
    854     
    855     int in[500005], out[500005];
    856     int dir[500005];
    857     
    858     void dfs2(int x, int p){
    859         chain[head[x]].pb(x);
    860         par[x] = p;
    861         weight[x] = 1;
    862         in[x] = tim++;
    863         for(int i : g[x]){
    864             head[i] = (i == g[x][0] ? head[x] : i);
    865             dfs2(i, x);
    866             if(i != g[x][0]) weight[x] += sub[i];
    867         }
    868         out[x] = tim - 1;
    869     }
    870     
    871     Matrix dp[500005]; 
    872     Matrix cum[500005];
    873     int rt[500005];
    874     int left0[500005], right0[500005], ppar[500005];
    875     
    876     int dnq(int l, int r, int p, const vector<int> &v){
    877         if(l > r) return 0;
    878         int sum = 0;
    879         for(int i = l; i <= r; i++) sum += weight[v[i]];
    880         int cur = 0;
    881         int mid = -1;
    882         for(int i = l; i <= r; i++){
    883             cur += weight[v[i]];
    884             if(cur >= sum/2){
    885                 mid = i;
    886                 break;
    887             }
    888         }
    889         if(p == -1) ppar[v[mid]] = v[mid];
    890         else ppar[v[mid]] = p;
    891         left0[v[mid]] = dnq(l, mid - 1, v[mid], v);
    892         right0[v[mid]] = dnq(mid + 1, r, v[mid], v);
    893         return v[mid];
    894     }
    895     
    896     void merge(int x){
    897         if(right0[x] && left0[x]){
    898             cum[x] = cum[left0[x]]*dp[x]*cum[right0[x]];
    899         } else if(left0[x] && !right0[x]){
    900             cum[x] = cum[left0[x]]*dp[x];
    901         } else if(right0[x] && !left0[x]){
    902             cum[x] = dp[x]*cum[right0[x]];
    903         } else {
    904             cum[x] = dp[x];
    905         }
    906     }
    907     
    908     void pull(int x){
    909         while(x != rt[x]){
    910             merge(x); 
    911             x = ppar[x];
    912         }
    913         merge(x);
    914     }
    915     
    916     ll a[500005], b[500005], c[500005];
    917     ll dp0[500005][3];
    918     
    919     void dfs3(int x){
    920         dp0[x][0] = a[x];
    921         dp0[x][2] = b[x] + c[x];
    922         ll deg1 = a[x] + c[x], deg2 = b[x] + a[x] + c[x];
    923         ll mn1 = LLINF, mn2 = LLINF;
    924         for(int i : g[x]){
    925             dfs3(i);
    926             dp0[x][0] += dp0[i][0];
    927             dp0[x][2] += dp0[i][2];
    928             deg1 += min(dp0[i][0], dp0[i][1]);
    929             deg2 += min({dp0[i][0], dp0[i][1], dp0[i][2]});
    930             mn1 = min(mn1, max((ll)0, dp0[i][1] - dp0[i][0]));
    931             mn2 = min(mn2, max((ll)0, min(dp0[i][1], dp0[i][2]) - dp0[i][0]));
    932         }
    933         dp0[x][1] = min(deg1 + mn1, deg2 + mn2);
    934     }
    935     
    936     fastset deg1[500005], deg2[500005];
    937     ll sum0[500005], sum2[500005], sum01[500005], sum012[500005];
    938     
    939     void rebuild(int x){
    940         dp[x][0][0] = a[x] + sum0[x];
    941         dp[x][0][1] = LLINF;
    942         dp[x][0][2] = LLINF;
    943         if(g[x].size()){
    944             dp[x][1][0] = min(a[x] + b[x] + c[x] + deg2[x].query() + sum012[x], a[x] + c[x] + deg1[x].query() + sum01[x]);
    945             dp[x][1][1] = min(a[x] + c[x] + sum01[x], a[x] + b[x] + c[x] + sum012[x]);
    946             dp[x][1][2] = a[x] + b[x] + c[x] + sum012[x];
    947         } else {
    948             dp[x][1][0] = dp[x][1][1] = dp[x][1][2] = LLINF;
    949         }
    950         dp[x][2][0] = LLINF;
    951         dp[x][2][1] = LLINF;
    952         dp[x][2][2] = b[x] + c[x] + sum2[x];
    953     }
    954     
    955     ll eval(int x, int ind){
    956         return min({cum[rt[x]][ind][0], cum[rt[x]][ind][1], cum[rt[x]][ind][2]});
    957     }
    958     
    959     void rem(int x){
    960         while(head[x] != 1){
    961             if(x == head[x]){
    962                 ll v0 = eval(x, 0), v1 = eval(x, 1), v2 = eval(x, 2);
    963                 deg1[par[x]].erase(max((ll)0, v1 - v0));
    964                 deg2[par[x]].erase(max((ll)0, min(v1, v2) - v0));
    965                 sum012[par[x]] -= min({v0, v1, v2});
    966                 sum01[par[x]] -= min(v0, v1);
    967                 sum0[par[x]] -= v0;
    968                 sum2[par[x]] -= v2;
    969                 x = par[x];
    970             }
    971             x = head[x];
    972         }
    973     }
    974     
    975     void add(int x){
    976         while(head[x] != 1){
    977             if(x == head[x]){
    978                 ll v0 = eval(x, 0), v1 = eval(x, 1), v2 = eval(x, 2);
    979                 deg1[par[x]].insert(max((ll)0, v1 - v0));
    980                 deg2[par[x]].insert(max((ll)0, min(v1, v2) - v0));
    981                 sum012[par[x]] += min({v0, v1, v2});
    982                 sum01[par[x]] += min(v0, v1);
    983                 sum0[par[x]] += v0;
    984                 sum2[par[x]] += v2;
    985                 rebuild(par[x]);
    986                 pull(par[x]);
    987                 x = par[x];
    988             }
    989             x = head[x];
    990         }
    991     }
    992     
    993     int main(){
    994         setIO();
    995         int t;
    996         cin >> t;
    997         while(t--){
    998             int n, q;
    999             cin >> n >> q;
   1000             for(int i = 2; i <= n; i++){
   1001                 int x;
   1002                 cin >> x;
   1003                 g[x].pb(i);
   1004             }
   1005             ll sum = 0;
   1006             for(int i = 1; i <= n; i++) cin >> b[i], sum += b[i];
   1007             dfs1(1);
   1008             head[1] = 1;
   1009             dfs2(1, 1);
   1010             dfs3(1);
   1011             for(int i = 1; i <= n; i++){
   1012                 if(chain[i].size()){
   1013                     int p = dnq(0, chain[i].size() - 1, -1, chain[i]);
   1014                     for(int j : chain[i]) rt[j] = p;
   1015                 }
   1016             }
   1017             for(int i = 1; i <= n; i++){
   1018                 deg1[i].insert(LLINF);
   1019                 deg2[i].insert(LLINF);
   1020                 for(int j : g[i]){
   1021                     if(head[j] == head[i]) continue;
   1022                     deg1[i].insert(max((ll)0, dp0[j][1] - dp0[j][0]));
   1023                     deg2[i].insert(max((ll)0, min(dp0[j][1], dp0[j][2]) - dp0[j][0]));
   1024                     sum012[i] += min({dp0[j][0], dp0[j][1], dp0[j][2]});
   1025                     sum01[i] += min(dp0[j][0], dp0[j][1]);
   1026                     sum0[i] += dp0[j][0];
   1027                     sum2[i] += dp0[j][2];
   1028                 }
   1029                 rebuild(i);
   1030                 pull(i);
   1031             } 
   1032             while(q--){
   1033                 int t, x, v;
   1034                 cin >> t >> x >> v;
   1035                 rem(x);
   1036                 if(t == 1) a[x] += v;
   1037                 else c[x] += v, sum += v;
   1038                 rebuild(x);
   1039                 pull(x);
   1040                 add(x);
   1041                 cout << (min({eval(1, 0), eval(1, 1), eval(1, 2)}) == sum ? "YES" : "NO") << "\n";
   1042             }
   1043             tim = 0;
   1044             for(int i = 1; i <= n; i++){
   1045                 a[i] = b[i] = c[i] = 0;
   1046                 g[i].clear();
   1047                 chain[i].clear();
   1048                 deg1[i].clear();
   1049                 deg2[i].clear();
   1050                 sum0[i] = sum2[i] = sum01[i] = sum012[i] = 0;
   1051             }
   1052         }
   1053     }
   1054 ```
   1055 
   1056 **Solution 2**
   1057 
   1058 There also exists a solution without flows. Thanks to [rainboy](/profile/rainboy "Master rainboy") for discovering it during testing!
   1059 
   1060 Lets greedily assign the growth events. We will always try to use the growth events to satisfy harvest events or required peaches in its subtree, and if there is any excess then we give it to the parent's required peaches. Similarly, we will always use harvest events on growth events in its subtree. Lets define a $dp[u]$ for each node $u$. If $dp[x] \gt 0$ then it means we can give $dp[u]$ growths to $u$'s parent. Otherwise, it means $dp[u]$ requires $-dp[u]$ growths from its ancestors. Let $pos_u$ denote the sum of positive $dp[v]$ where $v$ is a child a of $u$, and $neg_u$ denote the sum of negative $dp[v]$. First we used the excess growth to satisfy the required peaches, so we can set $b_u = \max(0, b_u - pos_u)$. Then we distribute the growth events at node $u$ to satisfy the requirements in the subtree. Define $a_i$ as the number of growth events on node $i$ and $c_i$ as the number of harvest events on node $i$. To account for the harvest events at node $i$, we can define $bal_u = \text{sum of } a_i \text{ in u's subtree} - \text{sum of } b_i \text{ in u's subtree} - \text{sum of } c_i \text{ in u's subtree}$. We know that $dp[u] \le bal_u$, and as it turns out, as long as we keep $bal_u$ as an upper bound on $dp[u]$, the harvest events will always be satisfied. Why? $a_u + neg_u - \max(0, b_u - pos_u)$ is the assignment of growth events without considering harvest events. The amount of unused growth events in the subtree of $u$ is given by $bal_u - (a_u + neg_u - \max(0, b_u - pos_u)) + c_u$. If $a_u + neg_u - \max(0, b_u - pos_u) \le bal_u$, then it means we can use all of our harvest events on unused growth events in the subtree. If $a_u + neg_u - \max(0, b_u - pos_u) \gt bal_u$, then it means we will use all of our harvest events but still have $bal_u - (a_u + neg_u - \max(0, b_u - pos_u))$ harvest events remaining. Thus, we can formulate our dp as $dp[u] = \min(a_u + neg_u - \max(0, b_u - pos_u), bal_u)$. Let $v$ be the heavy child of $u$ and $pos'_u$ be the sum of positive dp excluding $v$ and $neg'_u$ be the sum of positive dp excluding $v$. Then, we can rewrite our dp as $dp[u] = \min(dp[v] + a_u + neg'_u - \max(0, b_u - pos'_u), a_u + neg'_u, bal_u)$. Define $x_u = a_u + neg'_u - \max(0, b_u - pos'_u)$ and $y_u = a_u + neg'_u$. Then $dp[u] = \min(dp[v] + x_u, y_u, bal_u)$. This can be accelerated by representing the transition as a matrix and accelerating it using dynamic dp. However, we can also notice that the dp can be represented as the smallest $x_1 + x_2 + \ldots + x_{i - 1} + \min(y_i, bal_i)$ over all prefixes of each heavy light decomposition chain. Thus, we can maintain the dp by using a range add and prefix min segment tree.
   1061 
   1062 **Code (C++)**
   1063 
   1064 ```
   1065 #include <stdio.h>
   1066 #include <stdlib.h>
   1067 #include <string.h>
   1068 
   1069 #define N	300000
   1070 #define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N))) */
   1071 #define INF	0x3f3f3f3f3f3f3f3fLL
   1072 
   1073 long long min(long long a, long long b) { return a < b ? a : b; }
   1074 long long max(long long a, long long b) { return a > b ? a : b; }
   1075 
   1076 int *ej[N], eo[N], n;
   1077 
   1078 void append(int i, int j) {
   1079 	int o = eo[i]++;
   1080 
   1081 	if (o >= 2 && (o & o - 1) == 0)
   1082 		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
   1083 	ej[i][o] = j;
   1084 }
   1085 
   1086 int dd[N], pp[N], qq[N], jj[N], ta[N], tb[N], qu[N];
   1087 int bb[N]; long long aa[N], zz[N], zzp[N], zzn[N];
   1088 
   1089 int dfs1(int i, int d) {
   1090 	int o, s, k_, j_;
   1091 
   1092 	dd[i] = d;
   1093 	s = 1, k_ = 0, j_ = -1;
   1094 	zz[i] = -bb[i];
   1095 	for (o = eo[i]; o--; ) {
   1096 		int j = ej[i][o], k = dfs1(j, d + 1);
   1097 
   1098 		s += k;
   1099 		if (k_ < k)
   1100 			k_ = k, j_ = j;
   1101 		zz[i] += zz[j];
   1102 	}
   1103 	qq[i] = j_, jj[i] = j_ == -1 ? i : jj[j_];
   1104 	return s;
   1105 }
   1106 
   1107 int t_;
   1108 
   1109 void dfs2(int i, int q) {
   1110 	int o, j_;
   1111 
   1112 	qu[ta[i] = t_++] = i;
   1113 	j_ = qq[i], qq[i] = q;
   1114 	if (j_ != -1)
   1115 		dfs2(j_, q);
   1116 	for (o = eo[i]; o--; ) {
   1117 		int j = ej[i][o];
   1118 
   1119 		if (j != j_)
   1120 			dfs2(j, j);
   1121 	}
   1122 	tb[i] = t_;
   1123 }
   1124 
   1125 long long stx[N_ * 2], sty[N_ * 2], stz[N_ * 2], lz[N_]; int h_, n_;
   1126 
   1127 void put(int i, long long x) {
   1128 	stz[i] += x;
   1129 	if (i < n_)
   1130 		lz[i] += x;
   1131 }
   1132 
   1133 void pus(int i) {
   1134 	if (lz[i])
   1135 		put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = 0;
   1136 }
   1137 
   1138 void pul(int i) {
   1139 	if (!lz[i]) {
   1140 		int l = i << 1, r = l | 1;
   1141 
   1142 		stx[i] = stx[l] + stx[r];
   1143 		sty[i] = min(sty[l], stx[l] + sty[r]);
   1144 		stz[i] = min(stz[l], stx[l] + stz[r]);
   1145 	}
   1146 }
   1147 
   1148 void push(int i) {
   1149 	int h;
   1150 
   1151 	for (h = h_; h > 0; h--)
   1152 		pus(i >> h);
   1153 }
   1154 
   1155 void pull(int i) {
   1156 	while (i > 1)
   1157 		pul(i >>= 1);
   1158 }
   1159 
   1160 void build() {
   1161 	int i, j, a, o;
   1162         h_ = 0;
   1163 
   1164 	while (1 << h_ < n)
   1165 		h_++;
   1166 	n_ = 1 << h_;
   1167 	memset(stx, 0, n_ * 2 * sizeof *stx);
   1168 	memset(sty, 0, n_ * 2 * sizeof *sty);
   1169 	memset(stz, 0, n_ * 2 * sizeof *stz);
   1170 	memset(lz, 0, n_ * sizeof *lz);
   1171 	memset(aa, 0, n * sizeof *aa);
   1172 	memset(zzp, 0, n * sizeof *zzp);
   1173 	memset(zzn, 0, n * sizeof *zzn);
   1174 	for (i = 0; i < n; i++) {
   1175 		a = ta[i];
   1176 		stz[n_ + a] = zz[i];
   1177 		for (o = eo[i]; o--; ) {
   1178 			j = ej[i][o];
   1179 			if (qq[j] == j)
   1180 				zzn[i] += -zz[j];
   1181 		}
   1182 		stx[n_ + a] = -zzn[i] - bb[i];
   1183 		sty[n_ + a] = -zzn[i];
   1184 	}
   1185 	for (i = n_ - 1; i > 0; i--)
   1186 		pul(i);
   1187 }
   1188 
   1189 void upd(int i) {
   1190 	int i_ = n_ + ta[i];
   1191 
   1192 	push(i_);
   1193 	stx[i_] = aa[i] - zzn[i] - max(bb[i] - zzp[i], 0);
   1194 	sty[i_] = aa[i] - zzn[i];
   1195 	pull(i_);
   1196 }
   1197 
   1198 void update_z(int l, int r, long long x) {
   1199 	int l_ = l += n_, r_ = r += n_;
   1200 
   1201 	push(l_), push(r_);
   1202 	for ( ; l <= r; l >>= 1, r >>= 1) {
   1203 		if ((l & 1) == 1)
   1204 			put(l++, x);
   1205 		if ((r & 1) == 0)
   1206 			put(r--, x);
   1207 	}
   1208 	pull(l_), pull(r_);
   1209 }
   1210 
   1211 long long query(int l, int r) {
   1212 	long long xl, yl, zl, xr, yr, zr;
   1213 
   1214 	push(l += n_), push(r += n_);
   1215 	xl = 0, yl = INF, zl = INF, xr = 0, yr = INF, zr = INF;
   1216 	for ( ; l <= r; l >>= 1, r >>= 1) {
   1217 		if ((l & 1) == 1) {
   1218 			yl = min(yl, xl + sty[l]), zl = min(zl, xl + stz[l]), xl += stx[l];
   1219 			l++;
   1220 		}
   1221 		if ((r & 1) == 0) {
   1222 			yr = min(sty[r], yr == INF ? INF : stx[r] + yr), zr = min(stz[r], zr == INF ? INF : stx[r] + zr), xr += stx[r];
   1223 			r--;
   1224 		}
   1225 	}
   1226 	return min(min(xl + xr, min(yl, yr == INF ? INF : xl + yr)), min(zl, zr == INF ? INF : xl + zr));
   1227 }
   1228 
   1229 int main() {
   1230 	int t;
   1231 
   1232 	scanf("%d", &t);
   1233 	while (t--) {
   1234 		int q_, i, p, q;
   1235 
   1236 		scanf("%d%d", &n, &q_);
   1237 		for (i = 0; i < n; i++)
   1238 			ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
   1239 		pp[0] = -1;
   1240 		for (i = 1; i < n; i++) {
   1241 			scanf("%d", &pp[i]), pp[i]--;
   1242 			append(pp[i], i);
   1243 		}
   1244 		for (i = 0; i < n; i++)
   1245 			scanf("%d", &bb[i]);
   1246 		dfs1(0, 0);
   1247 		t_ = 0, dfs2(0, 0);
   1248 		build();
   1249 		while (q_--) {
   1250 			int t, x;
   1251 
   1252 			scanf("%d%d%d", &t, &i, &x), i--;
   1253 			if (t == 2)
   1254 				x = -x;
   1255 			if (t == 1)
   1256 				aa[i] += x, upd(i);
   1257 			while (i >= 0) {
   1258 				q = qq[i], p = pp[q];
   1259 				if (p >= 0) {
   1260 					if (zz[q] > 0)
   1261 						zzp[p] -= zz[q];
   1262 					else
   1263 						zzn[p] -= -zz[q];
   1264 				}
   1265 				update_z(ta[q], ta[i], x);
   1266 				zz[q] = query(ta[q], ta[jj[q]]);
   1267 				if (p >= 0) {
   1268 					if (zz[q] > 0)
   1269 						zzp[p] += zz[q];
   1270 					else
   1271 						zzn[p] += -zz[q];
   1272 					upd(p);
   1273 				}
   1274 				i = p;
   1275 			}
   1276 			printf(zz[0] >= 0 ? "YES\n" : "NO\n");
   1277 		}
   1278 		for (i = 0; i < n; i++)
   1279 			free(ej[i]);
   1280 	}
   1281 	return 0;
   1282 }
   1283 ```