codeforces-scrape

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

2101.md (45166B)


      1 Source: https://codeforces.com/blog/entry/142788
      2 
      3 Thank you for participating! We hope you enjoyed the problems and, most importantly, had fun!
      4 
      5 ## [2102A - Dinner Time](/contest/2102/problem/A "Codeforces Round 1024 (Div. 2)")
      6 
      7 **Hints**
      8 
      9 **Hint 1**
     10 
     11 If you have the first $p$ elements, what happens to the rest?
     12 
     13 **Hint 2**
     14 
     15 What happens if $n\%p\neq0$?
     16 
     17 **Hint 3**
     18 
     19 How can the fact that we can also use negative numbers be useful?
     20 
     21 **Solution**
     22 
     23 The first thing to realize is that if the first $p$ elements of the array are determined, the rest will be unique ($a_i = a_{i-p}$ to hold the sum). If $p$ divides $n$, there will be $\frac{n}{p}$ blocks, each summing to $q$, so their total sum which is $q\cdot \frac{n}{p}$ should be equal to $m$. If not, the incomplete block that is created at the end can be used to cover any difference in sum, so it's always possible!
     24 
     25 **Code (Python 3)**
     26 
     27 ```
     28 t = int(input())
     29 
     30 for _ in range(t):
     31     n, m, p, q = map(int, input().split())
     32     
     33     if n % p == 0 and (n // p) * q != m:
     34         print("NO")
     35     else:
     36         print("YES")
     37 ```
     38 
     39 **Bonus**
     40 
     41 This problem was supposed to be for cyclic arrays, and also required construction, but due to D2A difficulty it was adjusted!
     42 
     43 *Do you have a solution for the cyclic array version? Comment it below*
     44 
     45 ## [2102B - The Picky Cat](/contest/2102/problem/B "Codeforces Round 1024 (Div. 2)")
     46 
     47 **Hints**
     48 
     49 **Hint 1**
     50 
     51 Does the initial sign and order of elements matter?
     52 
     53 **Hint 2**
     54 
     55 If an element is before the median in the sorted array, can you shift it forward?
     56 
     57 **Hint 3**
     58 
     59 What if it is initially after the median?
     60 
     61 **Solution**
     62 
     63 Before starting, we take the absolute value of all elements since their signs do not matter. Then, if the first element of the array is equal to or smaller than the $\left\lfloor \frac{n}{2}\right\rfloor + 1$ smallest element of the array, the answer is possible. Else, it is impossible. The proof is as follows:
     64 
     65 * If the first element is equal to or smaller than the $\left\lceil\frac{n}{2}\right\rceil$ smallest element of the array, we can negate the big values until the first element becomes the $\left\lceil\frac{n}{2}\right\rceil$ smallest element of the array, hence becoming the median.
     66 * If the first element is equal to the $\left\lfloor \frac{n}{2}\right\rfloor + 1$ smallest element of the array, we can negate the entire array, which results in the first element becoming the $\left\lceil\frac{n}{2}\right\rceil$ smallest element of the array.
     67 * Otherwise, if the first element of the array is larger than the $\left\lfloor \frac{n}{2}\right\rfloor + 1$ smallest element of the array, negating values smaller than it has no effect, while negating values larger than it just makes the first element further away from the median position. You can verify that negating the first element itself does not help either by using similar cases.
     68 
     69 **Code (Python 3)**
     70 
     71 ```
     72 t = int(input())
     73 
     74 for _ in range(t):
     75     n = int(input())
     76     a = list(map(int, input().split()))
     77     
     78     pairs = [(abs(a[i]), i) for i in range(n)]
     79     pairs.sort()
     80     
     81     ans = [0] * n
     82     
     83     for i in range(n // 2 + 1):
     84         _, index = pairs[i]
     85         ans[index] = 1
     86     
     87     if ans[0]:
     88         print("YES")
     89     else:
     90         print("NO")
     91 ```
     92 
     93 **Bonus**
     94 
     95 Would it be easier to calculate the answer for all indices and just output for the first index?
     96 
     97 *What's up with the name of the problem?*
     98 
     99 ## [2101A - Mex in the Grid](/contest/2101/problem/A "Codeforces Round 1024 (Div. 1)")
    100 
    101 **Hints**
    102 
    103 **Hint 1**
    104 
    105 What is the MEX, if $0$ is not there?
    106 
    107 **Hint 2**
    108 
    109 When is the MEX equal to $k$?
    110 
    111 **Hint 3**
    112 
    113 If we want a subgrid to be included in as many other subgrids as possible, what shape should it have? What about its place?
    114 
    115 **Solution**
    116 
    117 The first fact to notice is that if the subgrid does not contain $0$, then the MEX is $0$ and we can ignore such subgrids. If the MEX is going to be $k$, it means **all** the values from $0$ to $k-1$ are included in the subgrid. For each $0\le k\le n^2$, we count how many subgrids have a MEX of at least $k$, aiming to maximize this.  
    118 To find the total sum of all MEX values, for each $k$ we count the number of subgrids that contain all the values from $0$ to $k-1$. Summing these counts gives us the final result.
    119 
    120 We claim that if our subgrid is nearly square (either a perfect square or a difference of $1$ in lengths), and is placed in the middle of the grid, then the answer is maximized.
    121 
    122 **Proof**: The multiplication of two numbers with the same sum is maximized when they are as close to each other as possible. Therefore, for each subgrid, if we consider the empty rows above and below it and separately consider the columns on its right and left, if one is fixed, the place is optimized to be in the middle. Now, similarly, we can say that it is optimal if the length and height of the subgrid are close to each other as well, as increasing one will cause the other one to decrease. With these two observations combined, a subgrid having the above properties is optimal when it's a *nearly* square subgrid in the middle of the grid.
    123 
    124 Any ordering with this property works; an easy example is a *spiral shape* that starts from the center of the grid and turns around itself.
    125 
    126 **Code (Python 3)**
    127 
    128 ```
    129 def magical_spiral(n):
    130     arr = [[-1] * n for _ in range(n)]
    131     
    132     if n % 2 == 0:
    133         x, y = n // 2 - 1, n // 2 - 1
    134     else:
    135         x, y = n // 2, n // 2
    136     
    137     arr[x][y] = 0
    138     value = step = 1
    139 
    140     dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    141 
    142     while value < n * n:
    143         for d in range(4):
    144             steps = step
    145             
    146             step += d % 2; dx, dy = dir[d]
    147 
    148             for _ in range(steps):
    149                 x += dx; y += dy
    150 
    151                 if 0 <= x < n and 0 <= y < n and arr[x][y] == -1:
    152                     arr[x][y] = value
    153                     value += 1
    154                 if value >= n * n:
    155                     break
    156             
    157             if value >= n * n:
    158                 break
    159 
    160     for row in arr:
    161         print(" ".join(str(num) for num in row))
    162     print()
    163 
    164 t = int(input())
    165 
    166 for _ in range(t):
    167     n = int(input())
    168 
    169     magical_spiral(n)
    170 ```
    171 
    172 **Bonus**
    173 
    174 We had the idea of dividing this problem into two subtasks, in which the second subtask requires you to **count** the sum of MEX of all subgrids!
    175 
    176 *Do you have a solution for this? Comment it below*
    177 
    178 ## [2101B - Quartet Swapping](/contest/2101/problem/B "Codeforces Round 1024 (Div. 1)")
    179 
    180 **Hints**
    181 
    182 **Hint 1**
    183 
    184 Is it possible for an element to change its index parity after some operations?
    185 
    186 **Hint 2**
    187 
    188 What else is not effected by the operation?
    189 
    190 **Hint 3**
    191 
    192 How to combine the above two properties under the time limit?
    193 
    194 **Solution**
    195 
    196 The first observation is that the parity of the position of the elements doesn't change with the operations. Thus, if an element is at an odd or even index in the initial permutation, it will retain the same parity in the final permutation. As long as we have four elements left, we can freely adjust them within their index parity zone, but what about the last three ones? We can see that the parity of the number of inversions is fixed, so by counting the inversions of the initial permutation, the order of the last four elements will be uniquely determined.
    197 
    198 **Code (C++)**
    199 
    200 ```
    201 #include <bits/stdc++.h>
    202 
    203 #define pb push_back
    204 #define int long long 
    205 #define F first
    206 #define S second
    207 #define sz(a) (int)a.size()
    208 #define pii pair<int,int> 
    209 #define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
    210 #define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
    211 #define all(a) a.begin(),a.end() 
    212 
    213 using namespace std ;
    214 const int maxn = 1e6 + 10 ;
    215 int a[maxn] , n , fen[maxn] ; 
    216 
    217 void upd(int x){
    218     while(x <= n){
    219         fen[x]++;
    220         x += x&-x;
    221     }
    222 }
    223 
    224 int que(int x){
    225     int ans =0 ;
    226     while(x){
    227         ans += fen[x] ;
    228         x -= x&-x;
    229     }
    230     return ans ; 
    231 }
    232 
    233 int f(vector<int> x){
    234     rep(i , 0, n)fen[i] =0;
    235     int ans =0 ;
    236     per(i , sz(x)-1 , 0){
    237         ans += que(x[i]);
    238         upd(x[i]) ;
    239     }
    240     
    241     return ans ; 
    242 }
    243 
    244 signed main(){
    245     ios::sync_with_stdio(0) ; cin.tie(0);
    246     
    247     int T ;
    248     cin >> T ;
    249     
    250     while(T--){
    251         vector <int> a1 , a2 ; 
    252         
    253         cin >> n ;
    254         rep(i ,1 ,n){
    255             int x; cin >> x; 
    256             
    257             if (i%2==1) {
    258                 a1.pb(x);
    259             } else {
    260                 a2.pb(x);
    261             }
    262         }    
    263         
    264         bool v = (f(a1)%2 != f(a2)%2);
    265         
    266         sort(all(a1)); sort(all(a2));
    267         
    268         int x1 = 0, x2 =0;    
    269         
    270         rep (i ,1 , n) {
    271             if (i%2==1) {
    272                 a[i] = a1[x1] ; x1++; 
    273             } else {
    274                 a[i] = a2[x2] ; x2++;
    275             }
    276         }
    277         
    278         if (v) {
    279             swap(a[n] , a[n-2]) ;
    280         }
    281         
    282         rep(i ,1 ,n) cout << a[i] << " ";
    283         cout << "\n";
    284     }
    285 }
    286 ```
    287 
    288 **Bonus**
    289 
    290 This problem was one of the first problems that we had, and the intended constraits were $n\le 3000$ as a D1A, but later was moved to D1B with $n\le 2\cdot 10^5$!
    291 
    292 *Do you know how to count the parity of inversions without counting the number of inversions?*
    293 
    294 ## [2101C - 23 Kingdom](/contest/2101/problem/C "Codeforces Round 1024 (Div. 1)")
    295 
    296 **Hints**
    297 
    298 **Hint 1**
    299 
    300 Does it matter if there are $2$ occurance of a number or $200$?
    301 
    302 **Hint 2**
    303 
    304 What greedy approaches can you think of?
    305 
    306 **Hint 3**
    307 
    308 Are they fast enough?
    309 
    310 **Solution**
    311 
    312 The first observation is that we only care about the first and last occurrences of each number in the final array, as anything in between doesn't change the maximum distance. Instead of counting the distances directly, the main idea of this problem is to break them down into pieces. For example, the distance of a pair $(i, j)$ such that $1\le i \lt j\le n$ and $a_i = a_j$ and also these indices are the farthest possible, instead of adding up $j-i$, we count one for each index in between $i$ and $j$. In Another word, for each index $i$, we count how many *begins* are in or before $i$, and how many *ends* are after $i$, adding up these values for each index gives us the sum of distances.
    313 
    314 For each prefix and suffix of our array, we count the maximum number of different *begins* that we can get greedily. It can be proven that if we try to match each $a_i$ with the biggest unmatched number left, we'll end up getting the maximum number of different matches possible. Doing so can be calculated in many different ways, one using sets is shown in the implementation below.
    315 
    316 After that, for each $1\le i \lt n$, we have a bound for the number of pairs that these indices can be in between of, as we calculated the maximum distinct matches possible for both sides (one prefix and one suffix). It can be proven that there exists an array $b$ meeting the problem conditions such that the bound for each index is held, and therefore summing up all values gives us the final answer.
    317 
    318 **Code (C++)**
    319 
    320 ```
    321 #include <bits/stdc++.h>
    322 
    323 #define int long long
    324 
    325 // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    326 // #pragma GCC optimize("O3")
    327 // #pragma GCC optimize("unroll-loops")
    328 
    329 #define F first 
    330 #define S second
    331 #define mp make_pair
    332 #define pb push_back
    333 #define all(x) x.begin(), x.end()
    334 #define kill(x) cout << x << "\n", exit(0);
    335 #define pii pair<int, int>
    336 #define pll pair<long long, long long>
    337 #define endl "\n"
    338  
    339  
    340  
    341 using namespace std;
    342 typedef long long ll;
    343 // typedef __int128_t lll;
    344 typedef long double ld;
    345 
    346 const int MAXN = (int)1e6 + 7;
    347 const int MOD = (int)1e9 + 7;
    348 const ll INF = (ll)1e18 + 7;
    349 
    350 int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, p, q, ans, flag;
    351 int arr[MAXN], f[MAXN][2];
    352 set<int> st;
    353 
    354 void solve() {
    355     cin >> n;
    356 
    357     for (int i=1; i<=n; i++) cin >> arr[i];
    358 
    359     for (int j=0; j<2; j++) {
    360         st.clear();
    361         for (int i=1; i<=n; i++) st.insert(i);
    362 
    363         for (int i=(j? n : 1); (j?i>1 : i<n); (j? i-- : i++)) {
    364             auto it = st.upper_bound(arr[i]);
    365 
    366             if (it != st.begin()) it--, st.erase(*it);
    367 
    368             f[i][j] = n-st.size();
    369         }
    370     }
    371     
    372     ans = 0;
    373     for (int i=1; i<n; i++) ans += min(f[i][0], f[i+1][1]);
    374 
    375     cout << ans << endl;
    376 }
    377 
    378 int32_t main() {
    379     #ifdef LOCAL
    380     freopen("inp.in", "r", stdin);
    381     freopen("res.out", "w", stdout);
    382     #else
    383     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    384     #endif
    385 
    386     cin >> t;
    387 
    388     while (t--) solve();
    389 
    390     return 0;
    391 }
    392 ```
    393 
    394 **Bonus**
    395 
    396 We thought every greedy approach for this problem is wrong, and the intended solution used to be a $O(n^3)$ DP, but later realized we were wrong!
    397 
    398 Can you think of a *rational* DP idea that despite the time limit can solve this question?
    399 
    400 ## [2101D - Mani and Segments](/contest/2101/problem/D "Codeforces Round 1024 (Div. 1)")
    401 
    402 **Hints**
    403 
    404 **Hint 1**
    405 
    406 What are some characteristics of a *cute* subarray?
    407 
    408 **Hint 2**
    409 
    410 Is *cuteness* a monotone property?
    411 
    412 **Hint 3**
    413 
    414 How to find the maximal *cute* subarray for a fixed index $i$?
    415 
    416 **Solution**
    417 
    418 The first observation is that a subarray is *cute*, iff there is an index $i$, such that it is the one and **only** share of the LIS and LDS, and all other elements belong to either LIS or LDS.
    419 
    420 ***Proof***: We know that there cannot be two elements belonging to both LIS and LDS, and if there is none, the property won't be held. Therefore, we conclude that there is *exactly* one element shared between the LIS and LDS.
    421 
    422 Diving deeper into the shared element, we can see that the smaller elements before it must all be ascending, and the bigger elements after it must also all be ascending (as this will make our LIS). Similarly, all the bigger elements before it and all the smaller elements after it should be descending. This gives us a good pattern, and we can easily see that any subarray *included* within a *cute* subarray is cute itself (call this monotonic property).
    423 
    424 For counting the total number of *cute* subarrays, we calculate the values of $R_i$ and $L_i$ for each index. Let $L_i$ be the **biggest** index before $i$, such that the condition above is met. Similarly define $R_i$ as the $smallest$ index after $i$. If we can somehow calculate this values for all indices, then we'll end up with $n$ segments (for each $1\le i\le n$), and a subarray is *cute* iff it's included in **at least** one segment. This is a very classic problem, so the solution won't be discussed here.
    425 
    426 The only detail left is how to calculate the values of $L_i$ and $R_i$? We'll discuss the process of calculating the $R_i$ here, but the $L_i$ follows a very similar pattern. We claim that $R_i = min(R_{i+1}, f(i))$. In here $f(i)$ is defined as follow:
    427 
    428 * if $a_i \gt a_{i+1}$: then $f(i)$ is minimum index $j$, such that $a_{i+1}\le a_j\le a_i$.
    429 * if $a_i \lt a_{i+1}$: in this case $f(i)$ is minimum $j$ such that $a_i\le a_j\le a_{i+1}$.
    430 
    431 ***Proof***: The fact that $R_i\le R_{i+1}$ can easily be concluded from the fact thay *cuteness* is a monotonic property. Also going back to the conditions described above, we can see that $f(i)$ is basically the first index that will ruin our condition, so based on the definition of $R_i$, we can say that $R_i = min(R_{i+1}, f(i))$.
    432 
    433 The calculation of $L_i$ and $R_i$ can both be implemented using a *Segment Tree* or a *Monotonic Stack*; both implementations are included below. After we have those values, we count the number of subarrays included in at least one segment, and that would be our final answer.
    434 
    435 **Codes**
    436 
    437 **Segment Tree Approach (C++)**
    438 
    439 ```
    440 #include <bits/stdc++.h>
    441  
    442 #define int long long
    443  
    444 // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    445 // #pragma GCC optimize("O3")
    446 // #pragma GCC optimize("unroll-loops")
    447  
    448  
    449 #define F first 
    450 #define S second
    451 #define mp make_pair
    452 #define pb push_back
    453 #define all(x) x.begin(), x.end()
    454 #define kill(x) cout << x << "\n", exit(0);
    455 #define pii pair<int, int>
    456 #define pll pair<long long, long long>
    457 #define endl "\n"
    458  
    459  
    460  
    461 using namespace std;
    462 typedef long long ll;
    463 typedef long double ld;
    464  
    465  
    466 const int MAXN = (int)1e6 + 7;
    467 const int MOD = 998244353;
    468 const int INF = (int)1e9 + 7;
    469  
    470  
    471 int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, q, ans, flag;
    472 int arr[MAXN], L[MAXN], R[MAXN];
    473  
    474  
    475 /* Segment Tree */
    476 #define mid ((l+r)>>1)
    477 #define lid (mid<<1)
    478 #define rid (lid|1)
    479  
    480  
    481 int seg[MAXN<<2];
    482  
    483  
    484 void build(int l=0, int r=n, int id=1) {
    485     if (l+1 == r) {
    486         if (!flag) seg[id] = INF;
    487         else seg[id] = -INF;
    488  
    489         return;
    490     }
    491  
    492     build(l, mid, lid);
    493     build(mid, r, rid);
    494  
    495     if (!flag) seg[id] = min(seg[lid], seg[rid]);
    496     else seg[id] = max(seg[lid], seg[rid]);
    497 }
    498  
    499  
    500 void upd(int ind, int k, int l=0, int r=n, int id=1) {
    501     if (l+1 == r) {
    502         seg[id] = k;
    503         return;
    504     }
    505  
    506     if (ind < mid) upd(ind, k, l, mid, lid);
    507     else upd(ind, k, mid, r, rid);
    508  
    509     if (!flag) seg[id] = min(seg[lid], seg[rid]);
    510     else seg[id] = max(seg[lid], seg[rid]);
    511 }
    512  
    513  
    514 int get(int s, int t, int l=0, int r=n, int id=1) {
    515     if (l >= r || s >= t) {
    516         if (!flag) return INF;
    517         else return -INF;
    518     }
    519  
    520     if (s <= l && t >= r) return seg[id];
    521     if (t <= mid) return get(s, t, l, mid, lid);
    522     if (s >= mid) return get(s, t, mid, r, rid);
    523     
    524     if (!flag) return min(get(s, t, l, mid, lid), get(s, t, mid, r, rid));
    525     else return max(get(s, t, l, mid, lid), get(s, t, mid, r, rid));
    526 }
    527  
    528 /* Segment Tree */
    529  
    530  
    531 void solve() {
    532     cin >> n;
    533  
    534     for (int i=1; i<=n; i++) {
    535         cin >> arr[i];
    536     }
    537  
    538     fill(L, L+n+7, 1);
    539     fill(R, R+n+7, n);
    540  
    541  
    542     flag = 0;
    543     build();
    544  
    545     for (int i=n-2; i>=1; i--) {
    546         upd(arr[i+2]-1, i+2);
    547  
    548         R[i] = min(R[i], get(min(arr[i], arr[i+1]), max(arr[i], arr[i+1]))-1);
    549     }
    550  
    551     flag = 1;
    552     build();
    553  
    554     for (int i=3; i<=n; i++) {
    555         upd(arr[i-2]-1, i-2);
    556  
    557         L[i] = max(L[i], get(min(arr[i], arr[i-1]), max(arr[i], arr[i-1]))+1);
    558     }
    559  
    560     for (int i=n-1; i>=1; i--) R[i] = min(R[i], R[i+1]);
    561     for (int i=2; i<=n; i++) L[i] = max(L[i], L[i-1]);
    562  
    563     ans = R[1];
    564  
    565     for (int i=2; i<=n; i++) {
    566         ans += R[i-1]-i+1;
    567         ans += (i-L[i]+1)*(R[i]-R[i-1]);
    568     }
    569  
    570     cout << ans << endl;
    571 }
    572  
    573  
    574  
    575 int32_t main() {
    576     #ifdef LOCAL
    577     freopen("inp.in", "r", stdin);
    578     freopen("res.out", "w", stdout);
    579     #else
    580     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    581     #endif
    582  
    583     cin >> t;
    584  
    585     while (t--) solve();
    586  
    587     return 0;
    588 }
    589 ```
    590 
    591 **Monotonic Stack Approach (C++)**
    592 
    593 ```
    594 #include <bits/stdc++.h>
    595  
    596 #define pb push_back
    597 #define int long long 
    598 #define F first
    599 #define S second
    600 #define sz(a) (int)a.size()
    601 #define pii pair<int,int> 
    602 #define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
    603 #define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
    604 #define all(a) a.begin(),a.end() 
    605  
    606 using namespace std ;
    607 const int maxn = 5e5 + 10 , mod = 1e9 + 7;
    608 int a[maxn] , ri[maxn] , le[maxn] , bl[maxn] , br[maxn] , sl[maxn] , sr[maxn] ;
    609  
    610  
    611 signed main(){
    612     ios::sync_with_stdio(0) ; cin.tie(0);
    613     
    614     int T;
    615     cin >> T;
    616     
    617     while(T--) {
    618         int n; cin >> n; 
    619         
    620         rep(i ,1, n) {
    621             cin >> a[i];
    622         }    
    623         
    624         vector <int> s , b; 
    625         
    626         rep(i , 1 ,n){
    627             while(sz(s) && a[s.back()] > a[i])s.pop_back() ;
    628             while(sz(b) && a[b.back()] < a[i])b.pop_back() ;
    629             
    630             sl[i] = (sz(s) ? s.back() : 0);
    631             bl[i] = (sz(b) ? b.back() : 0);    
    632             s.pb(i); b.pb(i) ;
    633         }
    634         
    635         s.clear();
    636         b.clear(); 
    637         
    638         per(i , n , 1){
    639             while(sz(s) && a[s.back()] > a[i])s.pop_back() ;
    640             while(sz(b) && a[b.back()] < a[i])b.pop_back() ;
    641             sr[i] = (sz(s) ? s.back() : n+1);
    642             br[i] = (sz(b) ? b.back() : n+1);    
    643             s.pb(i); b.pb(i) ;    
    644         }
    645         
    646         ri[n] = n;
    647         per(i , n-1 ,1){
    648             ri[i] = ri[i+1];        
    649             if(a[i] > a[i+1] && a[br[i+1]] < a[i]){
    650                 ri[i] = min(ri[i] , br[i+1]-1);
    651             }
    652             
    653             if(a[i] < a[i+1] && a[sr[i+1]] > a[i]){
    654                 ri[i] = min(ri[i] , sr[i+1]-1);
    655             }
    656         }
    657         
    658         
    659         le[1] = 1 ;
    660         rep(i , 2,n){
    661             le[i] = le[i-1] ;
    662             if(a[i] > a[i-1] && a[bl[i-1]] < a[i]){
    663                 le[i] = max(le[i] , bl[i-1]+1);
    664             }
    665             if(a[i] < a[i-1] && a[sl[i-1]] > a[i]){
    666                 le[i] = max(le[i] , sl[i-1]+1);
    667             }
    668         }
    669         
    670         int ans = ri[1] ;     
    671         rep(i , 2 , n){
    672             ans = (ans + (i-1 - le[i] + 1) * (ri[i] - ri[i-1]) + ri[i]-i+1) ;
    673         }
    674         cout << ans << "\n" ; 
    675     }
    676 }
    677 ```
    678 
    679 **Bonus**
    680 
    681 We ended up having two D1D difficulty problems, but in the end chose this one as it was more *cute*!
    682 
    683 We believe this was one of the *cleanest* problems we had. However, both the statement and solution made it look too classic, so we had a hard time making sure this idea had not been used elsewhere!
    684 
    685 *Do you have a different approach than ours? Tell us in the comments.*
    686 
    687 ## [2101E - Kia Bakes a Cake](/contest/2101/problem/E "Codeforces Round 1024 (Div. 1)")
    688 
    689 **Hints**
    690 
    691 **Hint 1**
    692 
    693 Can we see any node twice in our walk?
    694 
    695 **Hint 2**
    696 
    697 What is the upper bound on the length of the path?
    698 
    699 **Hint 3**
    700 
    701 How do we approach this using dynamic programming?
    702 
    703 **Hint 4**
    704 
    705 How to optimize the DP?
    706 
    707 **Solution**
    708 
    709 The length of each two nodes in a tree is *always* less than the number of nodes, and therefore the maximum weight that we can see in our constructed graph has an upper bound of $n-1$. Because the weight of any *nice* path is doubled every time, the maximum length of any *nice* path won't exceed $log_2(n)$.
    710 
    711 The next observation is that we cannot see any node twice in a nice path (in other words, there are no cycles).
    712 
    713 **Proof**: Let's assume that a cycle exists. We know that the weight of each edge is always greater than the sum of all previous edges, so even without any waste, $\sum_{i=0}^{k} 2^i \lt 2^{k+1}$. This tells us no matter how far we get, because we're taking more steps in the last edge than the sum of all previous ones, we can never end up in the first node. Therefore, every *nice* path is a simple path, and no cycles can be made.
    714 
    715 Now, let's define $dp_{i, j}$ as the **maximum weight** of any edge to start a simple path from vertex $j$ and take $i$ steps, and $0$ if not possible. The idea here is to build the nicest path reversly, from the end to the beginning. We can update this $dp$ and build the paths backwards, and this will give us an $O(n^2\cdot log(n))$ solution as $i\le log_2(n)$.
    716 
    717 To optimize this, we use the suffix trick on centroid decomposition and keep the maximum two suffixes every time, to update $dp_{i, ?}$ in increasing order of $i$ accordingly. This would result in a $O(n\cdot log(n)^3)$ implementation, which can be further optimized to $O(n\cdot log(n)^2)$ using the fact that we can use *counting sort* for sorting as we have an upper bound of $n$. Both implementations are included below.
    718 
    719 **Codes**
    720 
    721 **O(n*log(n)^2) implementation**
    722 
    723 ```
    724 #include <bits/stdc++.h>
    725  
    726 using namespace std;
    727  
    728 typedef long long ll;
    729 typedef long double ld;
    730 typedef pair<int,int> pii;
    731 typedef pair<ll,ll> pll;
    732  
    733 #define F first
    734 #define S second
    735 #define endl '\n'
    736 #define Mp make_pair
    737 #define pb push_back
    738 #define pf push_front
    739 #define size(x) (ll)x.size()
    740 #define all(x) x.begin(), x.end()
    741 #define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
    742  
    743 const int N = 2e5 + 100, lg = 18;
    744 const ll Mod = 1e9 + 7;
    745 const ll inf = 1e18 + 10;
    746  
    747 ll MOD(ll a, ll mod=Mod) {
    748     a%=mod; (a<0)&&(a+=mod); return a;
    749 }
    750 
    751 ll poww(ll a, ll b, ll mod=Mod) {
    752     ll res = 1;
    753     while(b > 0) {
    754         if(b%2 == 1) res = MOD(res * a, mod);
    755         b /= 2;
    756         a = MOD(a * a, mod);
    757     }
    758     return res;
    759 }
    760  
    761 int t, n, a[N], dp[lg + 1][N], gl, subt[N], mark[N];
    762 int h[N], T[N], pd[N], tag[N];
    763 vector<int> adj[N], centAdj[N];
    764  
    765 void init(int v, int p=0) {
    766     subt[v] = 1, h[v] = (p == 0 ? 0 : h[p] + 1);
    767     for(int u : adj[v]) {
    768         if(u == p || mark[u] == 1) continue;
    769         init(u, v);
    770         subt[v] += subt[u];
    771     }
    772 }
    773  
    774 int findCent(int v, int p=0) {
    775     for(int u : adj[v]) {
    776         if(u == p || mark[u] == 1) continue;
    777         if(subt[u] > subt[gl]/2) return findCent(u, v);
    778     }
    779     return v;
    780 }
    781  
    782 int createCentTree(int v) {
    783     gl = v;
    784     init(v);
    785     int cent = findCent(v);
    786     init(cent);
    787  
    788     mark[cent] = 1;
    789     for(int u : adj[cent]) {
    790         if(mark[u] == 1) continue;
    791         centAdj[cent].pb(createCentTree(u));
    792     }
    793  
    794     return cent;
    795 }
    796  
    797 struct node {
    798     pii mx1, mx2;
    799     node() {
    800         mx1 = {-1e9, -1}; mx2 = {-1e9, -2};
    801     }
    802 } suff[N];
    803  
    804 node util(node y, pii x) {
    805     if(y.mx1 < y.mx2) swap(y.mx1, y.mx2);
    806     if(y.mx1 < x) swap(y.mx1, x);
    807     
    808     if(y.mx2 < x) swap(y.mx2, x);
    809     if(y.mx1.S == y.mx2.S) swap(y.mx2, x);
    810     
    811     return y;
    812 }
    813  
    814 vector<int> vec;
    815 void dfs1(int v, int p=0) {
    816     // update v by gl
    817     if(2*h[v] <= T[gl]) pd[v] = max(pd[v], h[v]);
    818     // update gl by v
    819     if(2*h[v] <= T[v]) pd[gl] = max(pd[gl], h[v]);
    820     
    821     if(p == 0) tag[v] = 0;
    822     else if(p == gl) {
    823         tag[v] = v;
    824     } else tag[v] = tag[p];
    825     
    826     if(tag[v] != 0 && T[v] - h[v] * 2 >= 0) vec.pb(v);
    827  
    828     for(int u : adj[v]) {
    829         if(u == p || mark[u] == 1) continue;
    830         dfs1(u, v);
    831     }
    832 }
    833  
    834 void dfs2(int v, int p=0) {
    835     if(p != 0) {
    836         if(suff[2*h[v]].mx1.S != tag[v]) {
    837             pd[v] = max(pd[v], suff[2*h[v]].mx1.F + h[v]);
    838         } else {
    839             pd[v] = max(pd[v], suff[2*h[v]].mx2.F + h[v]);
    840         }
    841     }
    842  
    843     for(int u : adj[v]) {
    844         if(u == p || mark[u] == 1) continue;
    845         dfs2(u, v);
    846     }
    847 }
    848  
    849 void solve(int v) {
    850     init(v, 0);
    851  
    852     gl = v;
    853     dfs1(v);
    854  
    855     for(auto it : vec) {
    856         int wh = min(T[it] - 2*h[it], 2*subt[v]);
    857         suff[wh] = util(suff[wh], {h[it], tag[it]});
    858     }
    859     
    860     for(int i=2*subt[v]-1; i>=1; i--) {
    861         suff[i] = util(suff[i], suff[i+1].mx1);
    862         suff[i] = util(suff[i], suff[i+1].mx2);
    863     }
    864     
    865     dfs2(v);
    866     
    867     vec.clear();
    868     for(int i=0; i<=2*subt[v]+1; i++) suff[i] = node();
    869     mark[v] = 1;
    870     for(int u : centAdj[v]) {
    871         solve(u);
    872     }
    873 }
    874  
    875 void work() {
    876     cin>>n;
    877     
    878     for(int i=1; i<=n; i++) {
    879         char ch; cin>>ch;
    880         a[i] = (ch == '1');
    881     }
    882     
    883     for(int v,u,i=1; i<n; i++) {
    884         cin>>v>>u; adj[v].pb(u); adj[u].pb(v);
    885     }
    886  
    887     int rt = createCentTree(1);
    888     fill(mark, mark+n+2, 0);
    889     fill(h, h+n+2, 0);
    890         
    891     for(int i=1; i<=n; i++) dp[0][i] = (a[i]==1 ? 2*n : -1);
    892  
    893     for(int i=1; i<=lg; i++) {
    894         for(int j=1; j<=n; j++) {
    895             if(a[j] == 1) T[j] = dp[i-1][j];
    896             else T[j] = -1;
    897         }
    898  
    899         solve(rt);
    900  
    901         for(int j=1; j<=n; j++) {
    902             tag[j] = mark[j] = 0;
    903             dp[i][j] = pd[j];
    904             pd[j] = 0;
    905         } 
    906     }
    907  
    908     for(int i=1; i<=n; i++) {
    909         if(a[i] == 0) {cout<<-1<<' '; continue;}
    910         for(int j=lg; j>=0; j--) {
    911             if(dp[j][i] >= 1) {
    912                 cout<<j+1<<' ';
    913                 break;
    914             }
    915         }
    916     }
    917     cout<<endl;
    918 }
    919  
    920 void reset_work() {
    921     for(int i=0; i<=lg; i++) for(int j=1; j<=n; j++) dp[i][j] = 0;
    922  
    923     gl = 0;
    924     for(int i=0; i<=n+1; i++) {
    925         adj[i].clear();
    926         centAdj[i].clear();
    927         h[i] = T[i] = pd[i] = tag[i] = 0;
    928         subt[i] = mark[i] = 0;
    929     }
    930  
    931     return;
    932 }
    933  
    934 int main() {
    935     ios_base::sync_with_stdio(false), cin.tie(0);
    936  
    937     cin>>t;
    938     
    939     while(t--) {
    940         work();
    941         reset_work();
    942     }
    943  
    944     return 0;
    945 }
    946 ```
    947 
    948 **O(n*log(n)^3) implementation**
    949 
    950 ```
    951 #include <bits/stdc++.h>
    952 using namespace std;
    953 
    954 using ll  = long long;
    955 using ld  = long double;
    956 using pii = pair<int, int>;
    957 using pll = pair<long long, long long>;
    958 using ull = unsigned long long;
    959 
    960 #define X               first
    961 #define Y               second
    962 #define SZ(x)           int(x.size())
    963 #define all(x)          x.begin(), x.end()
    964 #define mins(a,b)       (a = min(a,b))
    965 #define maxs(a,b)       (a = max(a,b))
    966 #define pb              push_back
    967 #define Mp              make_pair
    968 #define lc              id<<1
    969 #define rc              lc|1
    970 #define mid             ((l+r)>>1)
    971 mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());
    972 
    973 const ll  INF = 1e9 + 23;
    974 const ll  MOD = 1e9 + 7;
    975 const int MXN = 7e4+2;
    976 const int LOG = 18;
    977 
    978 int n;
    979 string s;
    980 vector<int> g[MXN];
    981 int dp[LOG][MXN];
    982 
    983 bool dead[MXN];
    984 int sz[MXN];
    985 int get_sz(int v, int p=0) {
    986     sz[v] = 1;
    987     for(int u : g[v])
    988         if(!dead[u] && u!=p)
    989             sz[v] += get_sz(u, v);
    990     return sz[v];
    991 }
    992 int centroid(int v, int N, int p=0) {
    993     for(int u : g[v])
    994         if(!dead[u] && u!=p && sz[u]+sz[u]>N)
    995             return centroid(u, N, v);
    996     return v;
    997 }
    998 
    999 vector<pair<int, int>> U;
   1000 vector<pair<int, int>> G;
   1001 int h[MXN], par[MXN];
   1002 
   1003 void dfs(int i, int v, int p=0) {
   1004     if(s[v-1]=='1') {
   1005         G.pb({h[v]<<1, v});
   1006         if(dp[i-1][v]>=2*h[v]) U.pb({dp[i-1][v]-2*h[v], v});
   1007     }
   1008     for(int u : g[v])
   1009         if(!dead[u] && u!=p)
   1010             par[u] = par[v],
   1011             h[u] = h[v]+1,
   1012             dfs(i, u, v);
   1013 }
   1014 
   1015 void solve(int i, int v) {
   1016     dead[v=centroid(v,get_sz(v))] = 1;
   1017     U.clear();
   1018     G.clear();
   1019     h[v] = 0;
   1020     par[v] = v;
   1021     if(s[v-1]=='1') {
   1022         G.pb({h[v]<<1, v});
   1023         if(dp[i-1][v]>=2*h[v]) U.pb({dp[i-1][v]-2*h[v], v});
   1024     }
   1025     for(int u : g[v])
   1026         if(!dead[u]) {
   1027             par[u] = u;
   1028             h[u] = 1;
   1029             dfs(i, u);
   1030         }
   1031     sort(all(U), greater<>());
   1032     sort(all(G), greater<>());
   1033     int mx1=0, mx2=0, ptr=0;
   1034     for(auto [lim, u] : G) {
   1035         while(ptr<SZ(U) && U[ptr].X>=lim) {
   1036             if(mx1 && par[mx1]==par[U[ptr].Y]) {
   1037                 if(h[U[ptr].Y]>h[mx1]) mx1 = U[ptr].Y;
   1038             }
   1039             else if(mx2 && par[mx2]==par[U[ptr].Y]) {
   1040                 if(h[U[ptr].Y]>h[mx2]) mx2 = U[ptr].Y;
   1041                 if(h[mx2]>h[mx1]) swap(mx1, mx2);
   1042             }
   1043             else {
   1044                 if(!mx1 || h[U[ptr].Y]>h[mx1]) mx2=mx1, mx1=U[ptr].Y;
   1045                 else if(!mx2 || h[U[ptr].Y]>h[mx2]) mx2=U[ptr].Y;
   1046             }
   1047             ptr++;
   1048         }
   1049         if(mx1) {
   1050             if(mx1 && par[mx1]!=par[u]) maxs(dp[i][u], h[mx1]+h[u]);
   1051             else if(mx2) maxs(dp[i][u], h[mx2]+h[u]);
   1052         }
   1053     }
   1054     for(int u : g[v])
   1055         if(!dead[u])
   1056             solve(i, u);
   1057 }
   1058 
   1059 void Main() {
   1060     cin >> n >> s;
   1061     for(int i=1; i<=n; i++) g[i].clear();
   1062     for(int i=1,u,v; i<n; i++) {
   1063         cin >> u >> v;
   1064         g[u].pb(v);
   1065         g[v].pb(u);
   1066     }
   1067     for(int i=1; i<=n; i++)
   1068         if(s[i-1]=='1')
   1069             dp[0][i] = 2*n-2;
   1070         else
   1071             dp[0][i] = -1;
   1072     for(int i=1; i<LOG; i++) {
   1073         fill(dead+1, dead+n+1, 0);
   1074         fill(dp[i]+1, dp[i]+n+1, -1);
   1075         solve(i, 1);
   1076     }
   1077     for(int i=1; i<=n; i++)
   1078         if(s[i-1]=='1') {
   1079             for(int j=LOG-1; j>=0; j--)
   1080                 if(dp[j][i]!=-1) {
   1081                     cout << j+1 << ' ';
   1082                     break;
   1083                 }
   1084         }
   1085         else cout << "-1 ";
   1086     cout << '\n';
   1087 }
   1088 
   1089 int32_t main() {
   1090     cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
   1091     int T = 1;
   1092     cin >> T;
   1093     while(T--) Main();
   1094     return 0;
   1095 }
   1096 ```
   1097 
   1098 **Bonus**
   1099 
   1100 We aimed to kill $log(n)^3$ implementations but then ended up making some correct $log(n)^2$ ones *TLE*, and gave up!
   1101 
   1102 *What was your favorite part about this problem? Comment it below.*
   1103 
   1104 ## [2101F - Shoo Shatters the Sunshine](/contest/2101/problem/F "Codeforces Round 1024 (Div. 1)")
   1105 
   1106 **Hints**
   1107 
   1108 **Hint 1**
   1109 
   1110 What are some properties of such colored trees?
   1111 
   1112 **Hint 2**
   1113 
   1114 Is the farthest blue and red node unique?
   1115 
   1116 **Hint 3**
   1117 
   1118 Should we look for an $O(n^2)$ solution or optimizes a slower one?
   1119 
   1120 **Solution**
   1121 
   1122 **Note**: For the purpose of this editorial, the diameter of a colored tree is defined as a simple path with maximum coolness which has a blue and red node on each side.
   1123 
   1124 Let's say a node is *special* iff the distance of the farthest blue node from it plus the distance of the farthesrt red node is equal to the length of the diameter of the tree. We also define a *special* edge as an edge such that the distances of the farthes red nodes on both sides are equal, and the distances of the blue nodes on each side are also equal to each other. Something like this:
   1125 
   1126 ![ ](/predownloaded/c6/28/c6286345019c0d2840742211ebb7e0d31557fa6c.png)
   1127 
   1128 We can see that the sum of distances of the farthest blue and green plus one is the length of the diameter. We claim that if there is no special node in a colored tree, then there must be a special edge.
   1129 
   1130 **Proof**: If there is no special node in a tree, then that means the farthest red and blue node for each vertex are on one side of it. We know that if there is at least one blue and one red colored node, then we have a valid diameter, so considering each node *on* that diameter, becuase it is not a special node the farthest blue and red of it must be on one side, and this leasds us towards a speical edge, the formal proof is described later when discussing $T'$.
   1131 
   1132 Let's make some more observations. It's easy to see that the diameter of a tree is not necessarily unique, but an interesting fact is that every two valid diameters **must** intersect with each other.
   1133 
   1134 **Proof**: if not, consider the tree is rooted from the blue/red node of one diameter, this would trivially show us a new blue and red node that has a distance longer than our current diameter and therefore a contradiction.
   1135 
   1136 This gives us the idea that the intersection of *all* valid diameters is a non-empty simple path on the tree.
   1137 
   1138 **Proof**: Consider two diameters and take their intersection, then add the rest one by one and take the intersection of the intersections. If there are any two pairs with intersections that do not intersect, this means there exists a pair of valid diameters which do not intersect with each other, and this is against our hypothesis.
   1139 
   1140 Before continuing, you must have an idea so far that we are aiming to count the trees with special node based on their node, and others based on their special edge, but there is still ***a lot*** to discuss.
   1141 
   1142 Going back to the special nodes, it's easy to see that they must must be on our diameter, and what makes this more interesting is that they must be on all diameters! So, taking the simple path that was the intersection of all valid diameters, we know that all of our special nodes lie on this path.
   1143 
   1144 Getting deeper on special nodes, we can see that for a non-special node such as $v$, the farthest blue and red are both on the same subtree if we root the tree from $v$. This makes the sum of distances to farthest red plus the farthest blue result in a number **always** bigger than the actual length of our diameter (as there is a shared part). Call the child in which both the farthest red and blue lie on a *cool* child.
   1145 
   1146 Let's create another graph based on our tree (call it $T'$) that has identical nodes to the tree, and directed edges. For each non-special node, give a directed edge from the identical vertex in $T'$ to its *cool* child. It's easy to see that special nodes would not have any incoming edges to them in this new graph, but every non-special node has *at least* one.
   1147 
   1148 We can use this graph to formally prove almost everything. Let's start with the fact that why any tree without a special node has a special edge?
   1149 
   1150 **Proof**: No special edge means that there are $n$ nodes in our tree that each have an outgoing edge, therefore $n$ directed edges as well. Our initial tree had only $n-1$ edge, so therefore based on the pigeonhole principle, there must be an edge in the initial tree, that two directed edges pass above it. It's trivial that those edges cannot have the same direction, and therefore this will lead us to a directed cycle of length two. Well, think about it, this is exactly what a *special* edge is!
   1151 
   1152 So if no special node is there, now we know that there is **at least** one special edge there somewhere. Well, it appears that we also cannot have more than one special edge in a colored tree.
   1153 
   1154 **Proof**: If so, we know that both of them must appear *on* the diameter, and considering their placement, this will contradict the fact that the distance of red and blue from both sides must be equal.
   1155 
   1156 Combining both above observations, now we know that if there is no special node in the colored tree, then there is **exactly one** special edge there somewhere.
   1157 
   1158 Now let's solve the first sub-problem, which is how to solve the problem if there is no special node. Define $f(v, a, b)$ for a node $v$ as the number of colourings which the farthest blue has a distance of $a$, and the farthest red has a distance of $b$. How to calculate $f$? Define $g(v, a, b)$ as the same thing, but this time for the distance of ***at most*** $a$ for blue and ***at most*** $b$ for red. It's easy to see that if we somehow calculate $g(v, a, b)$, then the following equation holds: \begin{equation} f(v, a, b) = g(v, a, b) — g(v, a-1, b) — g(v, a, b-1) + g(v, a-1, b-1) \end{equation} And here's how we find $g(v, a, b)$:
   1159 
   1160 \begin{equation} g(v, a, b) = 3^{p\cdot q}\cdot 1^r \end{equation} Where $p$ is the number of nodes such as $u$ that have a distance less than or equal to $a$, $q$ is the number of nodes that have a distance bigger than $a$ but less than or equal to $b$, and $r$ is the number of nodes that have a distance more than $b$. Formally:
   1161 
   1162 $p = \#\{u \mid d(u, v) \le a \}$ $q = \#\{ u \mid a \lt d(u, v) \le b \}$ $r = \#\{ u \mid b \lt d(u, v) \}$
   1163 
   1164 This will so far give us an $O(n^3)$ solution, dw we'll optimize it further later. Now we count the result for each edge of the tree, considering it will be a special edge in some colourings. Call both sides of the edge $u$ and $v$ just like the diagram shown above. Assuming we have $f$ calculated for all nodes, the answer is: \begin{equation} \sum_{a=0}^{n} \sum_{b=0}^{n} f(u, a, b) \cdot f(v, a, b) \cdot (a + b + 1) \end{equation} We're halfway there! Before the optimizing part, the only question left is what if there is a special node?
   1165 
   1166 Let's define a *super-special* node a node that is special, and not only does it have the farthest blue and red on different sides, but also either a blue node with distance one less than the farthest blue, or a red node with distance one less than the farthest red.
   1167 
   1168 Using the same observations that we made earlier and a deeper understanding of $T'$, you can prove that there is **at least** one super-special node, also **at most** one super-special node, and therefore always exactly one super-special node if there exists at least one special node. For such trees, we aim to calculate the answer for them based on their super-special node.
   1169 
   1170 Make the tree rooted from an arbitrary node. Define $dp_{v, i, a, b, j}$ as if you're in vertext $v$, you iterated $i$ children, so far the farthest blue node has a distance of $a$, the farthest red node has a distance of $b$, and $j=0$ if these two don't belong to one subtree (if possible, preferably $0$), and $1$ otherwise. Iterate over new subtrees and use the $f$ function defined before to end up with a computable $O(n^4)$ implementation!
   1171 
   1172 Now add another dimension $k$ to the above DP to keep track of if there is any blue node with distance one less than the farthest blue, or a red node with distance one less than the farthest red. Note that this really doesn't change anything.
   1173 
   1174 The above DP, though correct, won't give us a good solution and is only explained for gaining deeper insight. After truly understanding what is going on and what we are looking for, we can break down the same idea and calculate it manually, which will result in a $O(n^2)$ solution in the end. The primary fact to notice is that if the number of edges between two farthest red vertices is even, then it can be proven that the middle vertex of this path is a special node, and if odd, the middle edge is a special edge. As explaining everything in detail takes forever, try to prove the things we missed yourself and ask if you encountered any issues.
   1175 
   1176 **Code (C++)**
   1177 
   1178 ```
   1179 #include <bits/stdc++.h>
   1180 using namespace std;
   1181 
   1182 using ll  = long long;
   1183 using ld  = long double;
   1184 using pii = pair<int, int>;
   1185 using pll = pair<long long, long long>;
   1186 using ull = unsigned long long;
   1187 
   1188 #define X               first
   1189 #define Y               second
   1190 #define SZ(x)           int(x.size())
   1191 #define all(x)          x.begin(), x.end()
   1192 #define mins(a,b)       (a = min(a,b))
   1193 #define maxs(a,b)       (a = max(a,b))
   1194 #define pb              push_back
   1195 #define Mp              make_pair
   1196 #define lc              id<<1
   1197 #define rc              lc|1
   1198 #define mid             ((l+r)>>1)
   1199 mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());
   1200 
   1201 const ll  INF = 1e9 + 23;
   1202 const ll  MOD = 998244353;
   1203 const int MXN = 3006;
   1204 const int LOG = 23;
   1205 
   1206 template<typename T>
   1207 inline T md(T x) { return x &mdash; (x>=MOD ? MOD : 0); }
   1208 template<typename T>
   1209 inline void fix(T &x) { x = md(x); }
   1210 
   1211 int n;
   1212 vector<int> g[MXN];
   1213 vector<int> H[MXN];
   1214 int cnt[MXN], pscnt[MXN];
   1215 ll red[MXN], redb[MXN];
   1216 ll two[MXN], thr[MXN], itwo[MXN];
   1217 ll ans;
   1218 ll ps[MXN];
   1219 
   1220 void dfs(int v, int h=0, int p=-1) {
   1221     cnt[h]++;
   1222     H[h].back()++;
   1223     for(int u : g[v])
   1224         if(u!=p)
   1225             dfs(u, h+1, v);
   1226 }
   1227 
   1228 void Main() {
   1229     cin >> n;
   1230     for(int i=1; i<=n; i++) g[i].clear();
   1231     ans = 0;
   1232     for(int i=0, u,v; i<n-1; i++) {
   1233         cin >> u >> v;
   1234         g[u].pb(v);
   1235         g[v].pb(u);
   1236     }
   1237     for(int v=1; v<=n; v++) {
   1238         for(int adj=-1; adj<SZ(g[v]); adj++) {
   1239             for(int i=0; i<n; i++) H[i].clear(), cnt[i]=0;
   1240             if(adj==-1) {
   1241                 cnt[0]++;
   1242                 for(int u : g[v]) {
   1243                     for(int i=0; i<n; i++) H[i].pb(0);
   1244                     dfs(u, 1, v);
   1245                 }
   1246             }
   1247             else {
   1248                 if(g[v][adj]<v) continue;
   1249                 for(int i=0; i<n; i++) H[i].pb(0);
   1250                 dfs(v, 0, g[v][adj]);
   1251                 for(int i=0; i<n; i++) H[i].pb(0);
   1252                 dfs(g[v][adj], 0, v);
   1253             }
   1254             pscnt[0] = cnt[0];
   1255             for(int i=1; i<n; i++) pscnt[i] = pscnt[i-1] + cnt[i];
   1256             red[0] = 1;
   1257             redb[0] = 1;
   1258             for(int i=1; i<n; i++) {
   1259                 red[i] = two[cnt[i]]-1;
   1260                 for(int a : H[i])
   1261                     fix(red[i] += MOD-(two[a]-1));
   1262                 redb[i] = md(thr[cnt[i]]-two[cnt[i]]+MOD);
   1263                 for(int a : H[i])
   1264                     fix(redb[i] += MOD-(thr[a]-two[a]+MOD)*two[cnt[i]-a]%MOD);
   1265             }
   1266             for(int i=0; i<n; i++) {
   1267                 ps[i] = red[i]*two[i==0?0:pscnt[i-1]]%MOD*(i+(adj!=-1))%MOD;
   1268                 if(i) fix(ps[i] += ps[i-1]);
   1269             }
   1270             for(int j=0; j<n; j++)
   1271                 fix(ans += thr[j==0?0:pscnt[j-1]]
   1272                         *(thr[cnt[j]]-two[cnt[j]]+MOD)%MOD
   1273                         *itwo[pscnt[j]]%MOD
   1274                         *(ps[n-1]-ps[j]+MOD)%MOD);
   1275             for(int i=0; i<n; i++) {
   1276                 ps[i] = red[i]*two[i==0?0:pscnt[i-1]]%MOD;
   1277                 if(i) fix(ps[i] += ps[i-1]);
   1278             }
   1279             for(int j=0; j<n; j++)
   1280                 fix(ans += thr[j==0?0:pscnt[j-1]]
   1281                         *(thr[cnt[j]]-two[cnt[j]]+MOD)%MOD
   1282                         *itwo[pscnt[j]]%MOD
   1283                         *j%MOD
   1284                         *(ps[n-1]-ps[j]+MOD)%MOD);
   1285             for(int i=0; i<n; i++) {
   1286                 ps[i] = redb[i]
   1287                         *thr[i==0?0:pscnt[i-1]]%MOD
   1288                         *itwo[pscnt[i]]%MOD
   1289                         *(i+(adj!=-1))%MOD;
   1290                 if(i) fix(ps[i] += ps[i-1]);
   1291             }
   1292             for(int j=1; j<n; j++)
   1293                 fix(ans += two[pscnt[j-1]]%MOD
   1294                         *(two[cnt[j]]-1)%MOD
   1295                         *ps[j-1]%MOD);
   1296             for(int i=0; i<n; i++) {
   1297                 ps[i] = redb[i]
   1298                         *thr[i==0?0:pscnt[i-1]]%MOD
   1299                         *itwo[pscnt[i]]%MOD;
   1300                 if(i) fix(ps[i] += ps[i-1]);
   1301             }
   1302             for(int j=1; j<n; j++)
   1303                 fix(ans += two[pscnt[j-1]]%MOD
   1304                         *(two[cnt[j]]-1)%MOD
   1305                         *j%MOD
   1306                         *ps[j-1]%MOD);
   1307             for(int i=0; i<n; i++) {
   1308                 fix(ans += (redb[i]-red[i]+MOD)*thr[i==0?0:pscnt[i-1]]%MOD*(i+i+(adj!=-1))%MOD);
   1309             }
   1310         }
   1311     }
   1312     cout << ans << '\n';
   1313 }
   1314 
   1315 int32_t main() {
   1316     cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
   1317     int T = 1;
   1318     cin >> T;
   1319     two[0] = 1;
   1320     for(int i=1; i<MXN; i++) two[i] = two[i-1]*2%MOD;
   1321     thr[0] = 1;
   1322     for(int i=1; i<MXN; i++) thr[i] = thr[i-1]*3%MOD;
   1323     itwo[0] = 1;
   1324     for(int i=1; i<MXN; i++) itwo[i] = itwo[i-1]*((MOD+1)/2)%MOD;
   1325     while(T--) Main();
   1326     return 0;
   1327 }
   1328 ```
   1329 
   1330 **Bonus**
   1331 
   1332 The intended solution was the $O(n^3)$ discussed with some further optimizations, but then a new $O(n^2)$ solution showed up that changed everything! We thought of dividing the problem into two subtasks, but didn't do so, as the observation required for the $O(n^2)$ solution was quite beautiful.
   1333 
   1334 Also, we would like to thank [Hamed_Ghaffari](/profile/Hamed_Ghaffari "Grandmaster Hamed_Ghaffari") for his contributions to this problem.