codeforces-scrape

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

1528.md (26644B)


      1 Source: https://codeforces.com/blog/entry/91058
      2 
      3 Hi, Codeforces!
      4 
      5 [1529A - Eshag Loves Big Arrays](/contest/1529/problem/A "Codeforces Round 722 (Div. 2)")
      6 
      7 problem idea and solution: [AmShZ](/profile/AmShZ "Grandmaster AmShZ")
      8 
      9 **editorial**
     10 
     11 Tutorial is loading...
     12 
     13 **official solution**
     14 
     15 ```
     16 // khodaya khodet komak kon
     17 # include <bits/stdc++.h>
     18  
     19 using namespace std;
     20  
     21 typedef long long                                        ll;
     22 typedef long double                                      ld;
     23 typedef pair <int, int>                                  pii;
     24 typedef pair <pii, int>                                  ppi;
     25 typedef pair <int, pii>                                  pip;
     26 typedef pair <pii, pii>                                  ppp;
     27 typedef pair <ll, ll>                                    pll;
     28  
     29 # define A                                               first
     30 # define B                                               second
     31 # define endl                                            '\n'
     32 # define sep                                             ' '
     33 # define all(x)                                          x.begin(), x.end()
     34 # define kill(x)                                         return cout << x << endl, 0
     35 # define SZ(x)                                           int(x.size())
     36 # define lc                                              id << 1
     37 # define rc                                              id << 1 | 1
     38  
     39 ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
     40  
     41 const int xn = 1e2 + 10;
     42 const int sq = 320;
     43 const int inf = 1e9 + 10;
     44 const ll INF = 1e18 + 10;
     45 const int mod = 1e9 + 7;//998244353;
     46 const int base = 257;
     47  
     48 int qq, n, a[xn], mn, ans;
     49  
     50 int main(){
     51 	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
     52 	cin >> qq;
     53 	while (qq --){
     54 		cin >> n, mn = inf, ans = 0;
     55 		for (int i = 1; i <= n; ++ i)
     56 			cin >> a[i], mn = min(mn, a[i]);
     57 		for (int i = 1; i <= n; ++ i)
     58 			ans += a[i] != mn;
     59 		cout << ans << endl;
     60 	}
     61  
     62 	return 0;
     63 }
     64 ```
     65 
     66 [1529B - Sifid and Strange Subsequences](/contest/1529/problem/B "Codeforces Round 722 (Div. 2)")
     67 
     68 problem idea and solution: [Davoth](/profile/Davoth "Candidate Master Davoth")
     69 
     70 **editorial**
     71 
     72 Tutorial is loading...
     73 
     74 **official solution**
     75 
     76 ```
     77 // khodaya khodet komak kon
     78 // Nightcall - London Grammer
     79 # include <bits/stdc++.h>
     80  
     81 using namespace std;
     82  
     83 typedef long long                                        ll;
     84 typedef long double                                      ld;
     85 typedef pair <int, int>                                  pii;
     86 typedef pair <pii, int>                                  ppi;
     87 typedef pair <int, pii>                                  pip;
     88 typedef pair <pii, pii>                                  ppp;
     89 typedef pair <ll, ll>                                    pll;
     90  
     91 # define A                                               first
     92 # define B                                               second
     93 # define endl                                            '\n'
     94 # define sep                                             ' '
     95 # define all(x)                                          x.begin(), x.end()
     96 # define kill(x)                                         return cout << x << endl, 0
     97 # define SZ(x)                                           int(x.size())
     98 # define lc                                              id << 1
     99 # define rc                                              id << 1 | 1
    100  
    101 ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
    102  
    103 const int xn = 1e5 + 10;
    104 const int xm = - 20 + 10;
    105 const int sq = 320;
    106 const int inf = 1e9 + 10;
    107 const ll INF = 1e18 + 10;
    108 const int mod = 1e9 + 7;//998244353;
    109 const int base = 257;
    110  
    111 int qq, n, a[xn], ans, mn;
    112 bool flag;
    113  
    114 int main(){
    115 	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    116  
    117 	cin >> qq;
    118 	while (qq --){
    119 		cin >> n, ans = 0;
    120 		for (int i = 1; i <= n; ++ i)
    121 			cin >> a[i], ans += (a[i] <= 0);
    122 		sort(a + 1, a + n + 1), mn = inf;
    123 		for (int i = 1; i <= n; ++ i)
    124 			if (a[i] > 0)
    125 				mn = min(mn, a[i]);
    126 		flag = (mn < inf);
    127 		for (int i = 2; i <= n; ++ i)
    128 			if (a[i] <= 0)
    129 				flag &= (a[i] - a[i - 1] >= mn);
    130 		if (flag)
    131 			cout << ans + 1 << endl;
    132 		else
    133 			cout << ans << endl;
    134 	}
    135  
    136 	return 0;
    137 }
    138 ```
    139 
    140 [1528A - Parsa's Humongous Tree](/contest/1528/problem/A "Codeforces Round 722 (Div. 1)")
    141 
    142 problem idea and solution: [shokouf](/profile/shokouf "Candidate Master shokouf"), [AmShZ](/profile/AmShZ "Grandmaster AmShZ")
    143 
    144 **editorial**
    145 
    146 Tutorial is loading...
    147 
    148 **official solution**
    149 
    150 ```
    151 // Call my Name and Save me from The Dark
    152 #include <bits/stdc++.h>
    153  
    154 using namespace std;
    155  
    156 typedef long long int ll;
    157 typedef pair<int, int> pii;
    158  
    159 #define SZ(x)                       (int) x.size()
    160 #define F                           first
    161 #define S                           second
    162  
    163 const int N = 2e5 + 10;
    164 ll dp[2][N]; int A[2][N], n; vector<int> adj[N];
    165  
    166 void DFS(int v, int p = -1) {
    167     dp[0][v] = dp[1][v] = 0;
    168     for (int u : adj[v]) {
    169         if (u == p) continue;
    170         DFS(u, v);
    171         dp[0][v] += max(abs(A[0][v] - A[1][u]) + dp[1][u], dp[0][u] + abs(A[0][v] - A[0][u]));
    172         dp[1][v] += max(abs(A[1][v] - A[1][u]) + dp[1][u], dp[0][u] + abs(A[1][v] - A[0][u]));
    173     }
    174 }
    175  
    176 void Solve() {
    177     scanf("%d", &n);
    178     for (int i = 1; i <= n; i++) scanf("%d%d", &A[0][i], &A[1][i]);
    179     fill(adj + 1, adj + n + 1, vector<int>());
    180     for (int i = 1; i < n; i++) {
    181         int u, v; scanf("%d%d", &u, &v);
    182         adj[u].push_back(v);
    183         adj[v].push_back(u);
    184     }
    185     DFS(1);
    186     printf("%lld\n", max(dp[0][1], dp[1][1]));
    187 }
    188  
    189 int main() {
    190     int t; scanf("%d", &t);
    191     while (t--) Solve();
    192     return 0;
    193 }
    194 ```
    195 
    196 [1528B - Kavi on Pairing Duty](/contest/1528/problem/B "Codeforces Round 722 (Div. 1)")
    197 
    198 problem idea and solution: [alireza_kaviani](/profile/alireza_kaviani "International Grandmaster alireza_kaviani")
    199 
    200 **editorial**
    201 
    202 Tutorial is loading...
    203 
    204 **official solution**
    205 
    206 ```
    207 #include <bits/stdc++.h>
    208 using namespace std;
    209  
    210 typedef long long ll;
    211 typedef pair<ll, ll> pll;
    212 typedef pair<int, int> pii;
    213  
    214 #define X first
    215 #define Y second
    216 #define endl '\n'
    217  
    218 const int N = 1e6 + 10;
    219 const int MOD = 998244353;
    220  
    221 int n, dp[N], S;
    222  
    223 int main() {
    224     ios_base::sync_with_stdio(false); cin.tie(nullptr);
    225     cin >> n;
    226     for (int i = 1; i <= n; i++) {
    227         for (int j = i + i; j <= n; j += i) {
    228             dp[j]++;
    229         }
    230     }
    231     dp[0] = S = 1;
    232     for (int i = 1; i <= n; i++) {
    233         dp[i] = (dp[i] + S) % MOD;
    234         S = (S + dp[i]) % MOD;
    235     }
    236     cout << dp[n] << endl;
    237     return 0;
    238 }
    239 ```
    240 
    241 [1528C - Trees of Tranquillity](/contest/1528/problem/C "Codeforces Round 722 (Div. 1)")
    242 
    243 problem idea and solution: [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382")
    244 
    245 **editorial**
    246 
    247 Tutorial is loading...
    248 
    249 **official solution**
    250 
    251 ```
    252 #include <bits/stdc++.h>
    253 #pragma GCC optimize ("O2,unroll-loops")
    254 //#pragma GCC optimize("no-stack-protector,fast-math")
    255  
    256 using namespace std;
    257 typedef long long ll;
    258 typedef long double ld;
    259 typedef pair<int, int> pii;
    260 typedef pair<pii, int> piii;
    261 typedef pair<ll, ll> pll;
    262 #define debug(x) cerr<<#x<<'='<<(x)<<endl;
    263 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
    264 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
    265 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
    266 #define all(x) x.begin(), x.end()
    267 #define pb push_back
    268 #define kill(x) return cout<<x<<'\n', 0;
    269  
    270 const int inf=1000000010;
    271 const ll INF=1000000000000001000LL;
    272 const int mod=1000000007;
    273 const int MAXN=300010, LOG=20;
    274  
    275 int n, m, k, u, v, x, y, t, a, b, ans;
    276 int par1[MAXN], par2[MAXN];
    277 int stt[MAXN], fnt[MAXN], timer;
    278 vector<int> G1[MAXN], G2[MAXN];
    279 set<pii> st;
    280  
    281 int Add(int v){
    282 	auto it=st.lower_bound({stt[v], v});
    283 	if (it!=st.end() && fnt[it->second]<=fnt[v]) return -2;
    284 	if (it==st.begin()) return -1;
    285 	--it;
    286 	int res=it->second;
    287 	if (fnt[v]>fnt[res]) return -1;
    288 	st.erase(it);
    289 	return res;
    290 }
    291 void dfs1(int node){
    292 	stt[node]=timer++;
    293 	for (int v:G2[node]) dfs1(v);
    294 	fnt[node]=timer;
    295 }
    296 void dfs2(int node){
    297 	int res=Add(node);
    298 	if (res!=-2) st.insert({stt[node], node});
    299 	ans=max(ans, (int)st.size());
    300 	for (int v:G1[node]) dfs2(v);
    301 	if (res!=-2){
    302 		st.erase({stt[node], node});
    303 		if (res!=-1) st.insert({stt[res], res});
    304 	}
    305 }
    306  
    307 void Solve(){
    308 	cin>>n;
    309 	for (int i=1; i<=n; i++) G1[i].clear(), G2[i].clear();
    310 	for (int i=2; i<=n; i++) cin>>par1[i], G1[par1[i]].pb(i);
    311 	for (int i=2; i<=n; i++) cin>>par2[i], G2[par2[i]].pb(i);
    312 	timer=1;
    313 	ans=0;
    314 	dfs1(1);
    315 	dfs2(1);
    316 	cout<<ans<<"\n";
    317 }
    318  
    319 int main(){
    320 	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    321 	//freopen("input.txt", "r", stdin);
    322 	//freopen("output.txt", "w", stdout);
    323 	int T;
    324 	cin>>T;
    325 	while (T--) Solve();
    326 	
    327 	return 0;
    328 }
    329 ```
    330 
    331 **better implementation of official solution: AaParsa**
    332 
    333 ```
    334 #include <bits/stdc++.h>
    335 using namespace std;
    336  
    337 typedef long long ll;
    338 typedef pair<ll, ll> pll;
    339 typedef pair<int, int> pii;
    340  
    341 #define X first
    342 #define Y second
    343 #define endl '\n'
    344  
    345 const int N = 3e5 + 10;
    346  
    347 int t, n, L[N], R[N], timer, now, ans;
    348 vector<int> Srsh[N], Msht[N];
    349 set<pii> st;
    350  
    351 void MshtDFS(int u) {
    352     L[u] = timer++;
    353     for (int v : Msht[u]) {
    354         MshtDFS(v);
    355     }
    356     R[u] = timer;
    357 }
    358  
    359 int ispar(int u, int v) {
    360     return L[u] <= L[v] && R[v] <= R[u];
    361 }
    362  
    363 void SrshDFS(int u) {
    364     int last = now;
    365     // add u
    366     auto it = st.lower_bound({L[u], 0});
    367     if (it != st.end())
    368         now += 1 - ispar(u, it->Y);
    369     if (it != st.begin()) {
    370         auto nxt = it--;
    371         now += 1 - ispar(it->Y, u);
    372         if (nxt != st.end())
    373             now -= 1 - ispar(it->Y, nxt->Y);
    374     }
    375     st.insert({L[u], u});
    376     ans = max(ans, now);
    377     // DFS
    378     for (int v : Srsh[u]) {
    379         SrshDFS(v);
    380     }
    381     // remove u
    382     st.erase({L[u], u});
    383     now = last;
    384 }
    385  
    386 int main() {
    387     ios_base::sync_with_stdio(false); cin.tie(nullptr);
    388     cin >> t;
    389     while (t --> 0) {
    390         cin >> n;
    391         for (int i = 1; i <= n; i++) {
    392             Srsh[i].clear();
    393             Msht[i].clear();
    394         }
    395         for (int u = 2; u <= n; u++) {
    396             int par; cin >> par;
    397             Srsh[par].push_back(u);
    398         }
    399         for (int u = 2; u <= n; u++) {
    400             int par; cin >> par;
    401             Msht[par].push_back(u);
    402         }
    403         timer = 0;
    404         MshtDFS(1);
    405         ans = now = 0;
    406         SrshDFS(1);
    407         cout << ans + 1 << endl;
    408     }
    409     return 0;
    410 }
    411 ```
    412 
    413 **python solution: Tet**
    414 
    415 ```
    416 #!/usr/bin/env python
    417 import os
    418 import sys
    419 from io import BytesIO, IOBase
    420  
    421 # region fastio
    422  
    423 BUFSIZE = 8192
    424  
    425  
    426 class FastIO(IOBase):
    427     newlines = 0
    428  
    429     def __init__(self, file):
    430         self._fd = file.fileno()
    431         self.buffer = BytesIO()
    432         self.writable = "x" in file.mode or "r" not in file.mode
    433         self.write = self.buffer.write if self.writable else None
    434  
    435     def read(self):
    436         while True:
    437             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
    438             if not b:
    439                 break
    440             ptr = self.buffer.tell()
    441             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
    442         self.newlines = 0
    443         return self.buffer.read()
    444  
    445     def readline(self):
    446         while self.newlines == 0:
    447             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
    448             self.newlines = b.count(b"\n") + (not b)
    449             ptr = self.buffer.tell()
    450             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
    451         self.newlines -= 1
    452         return self.buffer.readline()
    453  
    454     def flush(self):
    455         if self.writable:
    456             os.write(self._fd, self.buffer.getvalue())
    457             self.buffer.truncate(0), self.buffer.seek(0)
    458  
    459  
    460 class IOWrapper(IOBase):
    461     def __init__(self, file):
    462         self.buffer = FastIO(file)
    463         self.flush = self.buffer.flush
    464         self.writable = self.buffer.writable
    465         self.write = lambda s: self.buffer.write(s.encode("ascii"))
    466         self.read = lambda: self.buffer.read().decode("ascii")
    467         self.readline = lambda: self.buffer.readline().decode("ascii")
    468  
    469  
    470 sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    471 input = lambda: sys.stdin.readline().rstrip("\r\n")
    472     
    473 class FenwickTree:
    474     def __init__(self, x):
    475         """transform list into BIT"""
    476         self.bit = x
    477         for i in range(len(x)):
    478             j = i | (i + 1)
    479             if j < len(x):
    480                 x[j] += x[i]
    481     def update(self, idx, x):
    482         """updates bit[idx] += x"""
    483         while idx < len(self.bit):
    484             self.bit[idx] += x
    485             idx |= idx + 1
    486  
    487     def query(self, end):
    488         """calc sum(bit[:end])"""
    489         end += 1
    490         x = 0
    491         while end:
    492             x += self.bit[end - 1]
    493             end &= end - 1
    494         return x
    495  
    496     def findkth(self, k):
    497         """Find largest idx such that sum(bit[:idx]) <= k"""
    498         idx = -1
    499         for d in reversed(range(len(self.bit).bit_length())):
    500             right_idx = idx + (1 << d)
    501             if right_idx < len(self.bit) and k >= self.bit[right_idx]:
    502                 idx = right_idx
    503                 k -= self.bit[idx]
    504         return idx + 1
    505  
    506 g1 = []
    507 g2 = []
    508 st = []
    509 ft = []
    510  
    511 def dfs1(graph, start=0):
    512     n = len(graph)
    513     tim = 1
    514     visited = [False] * n    
    515     stack = [start]
    516     while stack:
    517         start = stack[-1]
    518         if not visited[start]:
    519             st[start] = tim
    520             tim = tim + 1
    521             visited[start] = True
    522             for child in graph[start]:
    523                 if not visited[child]:
    524                     stack.append(child)
    525         else:
    526             stack.pop()
    527             ft[start] = tim
    528  
    529  
    530  
    531 def Do(v):
    532     global ans , cnt , mem
    533     fen.update(st[v] , 1);
    534     if(fen.query(ft[v] - 1) - fen.query(st[v])):
    535         mem += [[v , 0 , 0]]
    536         return;
    537     u = fen2.query(st[v]);
    538     ok[v] = 1
    539     cnt += 1
    540     fen2.update(st[v] , v - u)
    541     fen2.update(ft[v] , u - v)
    542     mem += [[v , u , ok[u]]]
    543     cnt -= ok[u]
    544     ok[u] = 0
    545     return;
    546  
    547  
    548  
    549 def undo():
    550     global cnt , ans , mem
    551     [v , u , a] = mem[-1]
    552     if(a != 0):
    553         ok[u] = 1
    554         cnt += 1
    555     cnt -= 1
    556     ok[v] = 0
    557     fen.update(st[v] , -1)
    558     fen2.update(st[v] , u - v)
    559     fen2.update(ft[v] , v - u)
    560     mem.pop()
    561     return;
    562  
    563  
    564 def dfs(graph, start=0):
    565     global ans , cnt
    566     n = len(graph)
    567     visited = [False] * n   
    568     stack = [start]
    569     while stack:
    570         start = stack[-1]
    571         if not visited[start]:
    572             Do(start)
    573             ans = max(ans , cnt)
    574             visited[start] = True
    575             for child in graph[start]:
    576                 if not visited[child]:
    577                     stack.append(child)
    578         else:
    579             stack.pop()
    580             undo()
    581  
    582  
    583  
    584 def solve():
    585     global n, g1 , g2 , V , st , ft , fen , fen2 , mem , ok , cnt , ans 
    586     n = int(input())
    587     if(n == 1):
    588         print(1)
    589         exit(0)
    590     
    591     g1 = [] ; g2 = []
    592     
    593     for i in range(n):
    594         g1.append([])
    595         g2.append([])
    596     
    597     # 0 base 
    598     
    599     V = list(map(int , input().split()))
    600     
    601     for i in range ( 1 , n ):
    602         v = V[i - 1]-1
    603         g1[v].append(i)
    604     
    605     V = list(map(int , input().split()))    
    606     
    607     for i in range ( 1 , n ):
    608         v = V[i-1]-1
    609         g2[v].append(i)
    610     st = [0] * (n + 100)
    611     ft = [0] * (n + 100)
    612     fen = FenwickTree([0] * (n + 3))
    613     fen2 = FenwickTree([0] * (n + 3))
    614     mem = []
    615     ok = [0]*(n + 100)
    616     cnt = 0
    617     ans = 0
    618     dfs1(g2)
    619     dfs(g1)
    620     print(ans)
    621  
    622 q = int(input())
    623 for i in range (q):
    624     solve()
    625 ```
    626 
    627 **another O(n.log) solution with seg-tree: N.N_2004**
    628 
    629 ```
    630 #include<bits/stdc++.h>
    631 #define lc (id * 2)
    632 #define rc (id * 2 + 1)
    633 #define md ((s + e) / 2)
    634 #define dm ((s + e) / 2 + 1)
    635 #define ln (e - s + 1)
    636 using namespace std;
    637  
    638 typedef long long ll;
    639 const ll MXN = 3e5 + 10;
    640 const ll MXS = MXN * 4;
    641 ll n, timer, ans, Ans;
    642 ll lazy[MXS], seg[MXS];
    643 ll Stm[MXN], Ftm[MXN];
    644 vector<ll> adj[MXN][2];
    645 void Build(ll id = 1, ll s = 1, ll e = n){
    646     lazy[id] = -1, seg[id] = 0;
    647     if(ln > 1) Build(lc, s, md), Build(rc, dm, e);
    648 }
    649 void Shift(ll id, ll s, ll e){
    650     if(lazy[id] == -1) return;
    651     seg[id] = lazy[id];
    652     if(ln > 1) lazy[lc] = lazy[rc] = lazy[id];
    653     lazy[id] = -1;
    654 }
    655 void Upd(ll l, ll r, ll x, ll id = 1, ll s = 1, ll e = n){
    656     Shift(id, s, e);
    657     if(e < l || s > r) return;
    658     if(l <= s && e <= r){
    659         lazy[id] = x; Shift(id, s, e);
    660         return;
    661     }
    662     Upd(l, r, x, lc, s, md), Upd(l, r, x, rc, dm, e);
    663     seg[id] = max(seg[lc], seg[rc]);
    664 }
    665 ll Get(ll l, ll r, ll id = 1, ll s = 1, ll e = n){
    666     Shift(id, s, e);
    667     if(e < l || s > r) return 0;
    668     if(l <= s && e <= r) return seg[id];
    669     return max(Get(l, r, lc, s, md), Get(l, r, rc, dm, e));
    670 }
    671 void prep(ll u, ll par, ll f){
    672     Stm[u] = ++ timer;
    673     for(auto v : adj[u][f]){
    674         if(v != par) prep(v, u, f);
    675     }
    676     Ftm[u] = timer;
    677 }
    678 bool Is_Jad(ll j, ll u){
    679     return (Stm[j] <= Stm[u] && Ftm[u] <= Ftm[j]);
    680 }
    681 void DFS(ll u, ll par, ll f){
    682     ll j = Get(Stm[u], Ftm[u]);
    683     if(!j) Upd(Stm[u], Ftm[u], u), ans ++;
    684     else{
    685         if(Is_Jad(j, u)){
    686             Upd(Stm[j], Ftm[j], 0);
    687             Upd(Stm[u], Ftm[u], u);
    688         }
    689     }
    690     Ans = max(Ans, ans);
    691     for(auto v : adj[u][f]){
    692         if(v != par) DFS(v, u, f);
    693     }
    694     if(!j) Upd(Stm[u], Ftm[u], 0), ans --;
    695     else{
    696         if(Is_Jad(j, u)){
    697             Upd(Stm[u], Ftm[u], 0);
    698             Upd(Stm[j], Ftm[j], j);
    699         }
    700     }
    701 }
    702 void solve(){
    703     cin >> n, timer = ans = Ans = 0;
    704     for(int i = 1; i <= n; i ++) adj[i][0].clear(), adj[i][1].clear();
    705     for(int t = 0; t < 2; t ++) for(int u = 2, v; u <= n; u ++){
    706         cin >> v, adj[v][t].push_back(u), adj[u][t].push_back(v);
    707     }
    708     Build(), prep(1, 0, 1);
    709     DFS(1, 0, 0);
    710     cout << Ans << '\n';
    711 }
    712 int main(){
    713     ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    714     ll q; cin >> q;
    715     while(q --) solve();
    716     return 0;
    717 }
    718 /*!
    719     HE'S AN INSTIGATOR,
    720     ENEMY ELIMINATOR,
    721     AND WHEN HE KNOCKS YOU BETTER
    722     YOU BETTER LET HIM IN.
    723 */
    724 //! N.N
    725 ```
    726 
    727 [1528D - It's a bird! No, it's a plane! No, it's AaParsa!](/contest/1528/problem/D "Codeforces Round 722 (Div. 1)")
    728 
    729 problem idea and solution: [AmShZ](/profile/AmShZ "Grandmaster AmShZ"), [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382")
    730 
    731 **editorial**
    732 
    733 Tutorial is loading...
    734 
    735 **official solution**
    736 
    737 ```
    738 #include <bits/stdc++.h>
    739 #pragma GCC optimize ("O2,unroll-loops")
    740 //#pragma GCC optimize("no-stack-protector,fast-math")
    741  
    742 using namespace std;
    743 typedef long long ll;
    744 typedef long double ld;
    745 typedef pair<int, int> pii;
    746 typedef pair<pii, int> piii;
    747 typedef pair<ll, ll> pll;
    748 #define debug(x) cerr<<#x<<'='<<(x)<<endl;
    749 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
    750 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
    751 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
    752 #define all(x) x.begin(), x.end()
    753 #define pb push_back
    754 #define kill(x) return cout<<x<<'\n', 0;
    755  
    756 const int inf=1000000010;
    757 const ll INF=1000000000000001000LL;
    758 const int mod=1000000007;
    759 const int N=605;
    760  
    761 int n, m, k, u, v, x, y, t, a, b;
    762 bool mark[N];
    763 int G[N][N], D[N];
    764 
    765 inline void upd(int &x, int y){ if (x>y) x=y;}
    766 
    767 int main(){
    768 	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    769 	memset(G, 63, sizeof(G));
    770 	cin>>n>>m;
    771 	while (m--){
    772 		cin>>u>>v>>x;
    773 		G[u][v]=min(G[u][v], x);
    774 	}
    775 	for (int i=0; i<n; i++){
    776 		memset(D, 63, sizeof(D));
    777 		memset(mark, 0, sizeof(mark));
    778 		for (int v=0; v<n; v++) upd(D[v], G[i][v]);
    779 		while (1){
    780 			int v=-1;
    781 			for (int x=0; x<n; x++) if (!mark[x]){
    782 				if (v==-1 || D[v]>D[x]) v=x;
    783 			}
    784 			if (v==-1) break ;
    785 			mark[v]=1;
    786 			upd(D[(v+1)%n], D[v]+1);
    787 			for (int u=0; u<n; u++)
    788 				upd(D[(u+D[v])%n], D[v]+G[v][u]);
    789 			
    790 		}
    791 		for (int j=0; j<n; j++){
    792 			if (i==j) cout<<"0 ";
    793 			else cout<<D[j]<<" ";
    794 		}
    795 		cout<<"\n";
    796 	}
    797 	
    798 	return 0;
    799 }
    800 ```
    801 
    802 **a different O(n^3) solution: Atreus**
    803 
    804 ```
    805 #include <bits/stdc++.h>
    806  
    807 using namespace std;
    808  
    809 typedef long long ll;
    810  
    811 const int maxn = 600 + 5;
    812  
    813 int n;
    814 int dp[maxn];
    815 bool mark[maxn];
    816 vector<pair<int,int>> g[maxn];
    817 int go[maxn];
    818  
    819 int dis(int s, int t) {
    820 	if (s <= t)
    821 		return t - s;
    822 	return n - (s - t);
    823 }
    824  
    825 void dijkstra(int src) {
    826 	memset(dp, 63, sizeof dp);
    827 	memset(mark, 0, sizeof mark);
    828 	dp[src] = 0;
    829 	set<int> S;
    830 	for (int i = 0; i < n; i++)
    831 		S.insert(i);
    832 	for (int i = 0; i < n - 1; i++) {
    833 		int v = -1;
    834 		for (int j = 0; j < n; j++) {
    835 			if (mark[j])
    836 				continue;
    837 			if (v == -1 or dp[v] > dp[j])
    838 				v = j;
    839 		}
    840 		S.erase(v);
    841 		mark[v] = 1;
    842 		if (v != src) {
    843 			auto it = S.lower_bound(v);
    844 			if (it == S.end())
    845 				it = S.lower_bound(0);
    846 			int nex = *it;
    847 			dp[nex] = min(dp[nex], dp[v] + dis(v, nex));
    848 		}
    849 		for (int i = 2 * n - 1; i >= 0; i--) {
    850 			int v = i % n;
    851 			if (!mark[v])
    852 				go[v] = v;
    853 			else
    854 				go[v] = go[(v + 1) % n];
    855 		}
    856 		for (auto [u, w] : g[v]) {
    857 			int nex = go[(u + dp[v]) % n];
    858 			dp[nex] = min(dp[nex], dp[v] + w + dis((u + dp[v]) % n, nex));
    859 		}
    860 	}
    861 }
    862  
    863 int main() {
    864 	ios_base::sync_with_stdio(false);
    865 	int m;
    866 	cin >> n >> m;
    867 	for (int i = 0; i < m; i++) { 
    868 		int v, u, w;
    869 		cin >> v >> u >> w;
    870 		g[v].push_back({u, w});
    871 	}
    872 	for (int i = 0; i < n; i++) {
    873 		dijkstra(i);
    874 		for (int j = 0; j < n; j++)
    875 			cout << dp[j] << " \n"[j == n-1];
    876 	}
    877 }
    878 ```
    879 
    880 [1528E - Mashtali and Hagh Trees](/contest/1528/problem/E "Codeforces Round 722 (Div. 1)")
    881 
    882 problem idea and solution: [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382")
    883 
    884 Thanks to [Kininarimasu](/profile/Kininarimasu "Master Kininarimasu") for the editorial.
    885 
    886 **editorial**
    887 
    888 Tutorial is loading...
    889 
    890 **official solution**
    891 
    892 ```
    893 #include <bits/stdc++.h>
    894 #pragma GCC optimize ("O2,unroll-loops")
    895 //#pragma GCC optimize("no-stack-protector,fast-math")
    896  
    897 using namespace std;
    898 typedef long long ll;
    899 typedef long double ld;
    900 typedef pair<int, int> pii;
    901 typedef pair<pii, int> piii;
    902 typedef pair<ll, ll> pll;
    903 #define debug(x) cerr<<#x<<'='<<(x)<<endl;
    904 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
    905 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
    906 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
    907 #define all(x) x.begin(), x.end()
    908 #define pb push_back
    909 #define kill(x) return cout<<x<<'\n', 0;
    910  
    911 const int inf=1000000010;
    912 const ll INF=1000000000000001000LL;
    913 const int mod=998244353, inv6=166374059;
    914 const int MAXN=1000010, LOG=20;
    915  
    916 ll n, m, k, u, v, x, y, t, a, b, ans;
    917 ll dp[MAXN], ps[MAXN];
    918 ll pd[MAXN], sp[MAXN];
    919  
    920 ll C3(ll x){
    921 	return x*(x-1)%mod*(x-2)%mod*inv6%mod;
    922 }
    923 ll C2(ll x){
    924 	return x*(x-1)/2%mod;
    925 }
    926  
    927 int main(){
    928 	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    929 	//freopen("input.txt", "r", stdin);
    930 	//freopen("output.txt", "w", stdout);
    931 	cin>>n;
    932 	dp[0]=ps[0]=1;
    933 	pd[0]=sp[0]=1;
    934 	for (int i=1; i<=n; i++){
    935 		ps[i]=(1 + ps[i-1] + ps[i-1]*(ps[i-1]+1)/2)%mod;
    936 		dp[i]=ps[i]-ps[i-1];
    937 		pd[i]=dp[i]-dp[i-1];
    938 		sp[i]=(sp[i-1]+pd[i])%mod;
    939 	}
    940 	for (int i=0; i<n; i++) ans=(ans + pd[i]*sp[n-1-i])%mod;
    941 	
    942 	ans=(ans + 2*C3(ps[n-1]+2))%mod;
    943 	if (n>=2) ans=(ans - 2*C3(ps[n-2]+2))%mod;
    944 	
    945 	ans=(ans + 2*C2(ps[n-1]+1))%mod;
    946 	if (n>=2) ans=(ans - 2*C2(ps[n-2]+1))%mod;
    947 	
    948 	if (ans<0) ans+=mod;
    949 	cout<<ans<<"\n";
    950 	
    951 	return 0;
    952 }
    953 ```
    954 
    955 [1528F - AmShZ Farm](/contest/1528/problem/F "Codeforces Round 722 (Div. 1)")
    956 
    957 problem idea and solution: [AmShZ](/profile/AmShZ "Grandmaster AmShZ"), [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382")
    958 
    959 **editorial**
    960 
    961 Tutorial is loading...
    962 
    963 **official solution**
    964 
    965 ```
    966 # include <bits/stdc++.h>
    967  
    968 using namespace std;
    969  
    970 typedef long long                                        ll;
    971 typedef long double                                      ld;
    972 typedef pair <int, int>                                  pii;
    973 typedef pair <pii, int>                                  ppi;
    974 typedef pair <int, pii>                                  pip;
    975 typedef pair <pii, pii>                                  ppp;
    976 typedef pair <ll, ll>                                    pll;
    977  
    978 # define A                                               first
    979 # define B                                               second
    980 # define endl                                            '\n'
    981 # define sep                                             ' '
    982 # define all(x)                                          x.begin(), x.end()
    983 # define kill(x)                                         return cout << x << endl, 0
    984 # define SZ(x)                                           int(x.size())
    985 # define lc                                              id << 1
    986 # define rc                                              id << 1 | 1
    987 # define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    988  
    989 ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
    990  
    991 const int xn = 3e5 + 10;
    992 const int xm = 18;
    993 const int sq = 320;
    994 const int inf = 1e9 + 10;
    995 const ll INF = 1e18 + 10;
    996 const int mod = 998244353;
    997 const int base = 257;
    998  
    999 int n, k, C[xn], ans, A[xn], B[xn], rev[xn];
   1000 int fact[xn], ifact[xn];
   1001  
   1002 void NTT(int *A, bool inv){
   1003 	int n = (1 << xm);
   1004 	for (int i = 0; i < (1 << xm); ++ i)
   1005 		if (rev[i] < i)
   1006 			swap(A[i], A[rev[i]]);
   1007 	for (int ln = 1; ln < n; ln <<= 1){
   1008 		int w = power(3, mod / 2 / ln, mod);
   1009 		if (inv)
   1010 			w = power(w, mod - 2, mod);
   1011 		for (int i = 0; i < n; i += ln + ln){
   1012 			int wn = 1;
   1013 			for (int j = i; j < i + ln; ++ j){
   1014 				int x = A[j], y = 1ll * A[j + ln] * wn % mod;
   1015 				A[j] = (x + y) % mod;
   1016 				A[j + ln] = (x - y + mod) % mod;
   1017 				wn = 1ll * wn * w % mod;
   1018 			}
   1019 		}
   1020 	}
   1021 	if (inv){
   1022 		int invn = power(1 << xm, mod - 2, mod);
   1023 		for (int i = 0; i < n; ++ i)
   1024 			A[i] = 1ll * A[i] * invn % mod;
   1025 	}
   1026 }
   1027  
   1028 int main(){
   1029 	InTheNameOfGod;
   1030 	
   1031 	cin >> n >> k;
   1032 	C[0] = fact[0] = 1;
   1033 	for (int i = 1; i < xn; ++ i){
   1034 		C[i] = 1ll * C[i - 1] * (n - i + 1) % mod * power(i, mod - 2, mod) % mod;
   1035 		fact[i] = 1ll * fact[i - 1] * i % mod;
   1036 	}
   1037 	ifact[xn - 1] = power(fact[xn - 1], mod - 2, mod);
   1038 	for (int i = xn - 2; i >= 0; -- i)
   1039 		ifact[i] = 1ll * ifact[i + 1] * (i + 1) % mod;
   1040 	for (int i = 1; i < (1 << xm); ++ i)
   1041 		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (xm - 1));
   1042 	for (int i = 0; i <= k; ++ i){
   1043 		A[i] = 1ll * power(i, k, mod) * ifact[i] % mod;
   1044 		B[i] = ifact[i];
   1045 		if (i % 2)
   1046 			B[i] = (mod - B[i]) % mod;
   1047 	}
   1048 	NTT(A, 0), NTT(B, 0);
   1049 	for (int i = 0; i < xn; ++ i)
   1050 		A[i] = 1ll * A[i] * B[i] % mod;
   1051 	NTT(A, 1);
   1052 	for (int i = 1; i <= k; ++ i)
   1053 		ans = (ans + 1LL * A[i] * C[i] % mod * power(n + 1, n - i, mod) % mod * fact[i] % mod) % mod;
   1054 	cout << ans << endl;
   1055  
   1056 	return 0;
   1057 }
   1058 ```