1981.md (19265B)
1 Source: https://codeforces.com/blog/entry/129848 2 3 Thank you for participating! Sorry for being much harder than usual Div. 2 :( But we still hope you find some of our problems interesting. 4 5 **Rating predictions (Inspired by sum's editorial)** 6 7 It seems like a joke now... 8 9 | Person | A | B | C | D | E | F | 10 | --- | --- | --- | --- | --- | --- | --- | 11 | [zltzlt](/profile/zltzlt "Grandmaster zltzlt") | 800 | 1400 | 1600 | 2000 | 2300 | 2800 | 12 | [small_peter](/profile/small_peter "Master small_peter") | 800 | 1400 | 1700 | 1600 | | | 13 | [WRuperD](/profile/WRuperD "Expert WRuperD") | 800 | 1300 | 1600 | 2000 | | 2800 | 14 | [yinhee](/profile/yinhee "Candidate Master yinhee") | 800 | 1000 | 1500 | 2100 | 2200 | 2700 | 15 | [sinsop90](/profile/sinsop90 "Candidate Master sinsop90") | 1000 | 1300 | 1500 | 2000 | 2200 | | 16 | [CutieSmileHaruka](/profile/CutieSmileHaruka "Master CutieSmileHaruka") | 800 | 1100 | 1600 | 1900 | | 2700 | 17 | [CharlieV](/profile/CharlieV "International Grandmaster CharlieV") | | | | 2400 | 2500 | 3000 | 18 | [JWRuixi](/profile/JWRuixi "Master JWRuixi") | | | | 1800 | | | 19 | [Edwin__VanCleef](/profile/Edwin__VanCleef "Expert Edwin__VanCleef") | | | 1600 | 1800 | | 20 | [QwQwf](/profile/QwQwf "Candidate Master QwQwf") | 1000 | 1600 | 2000 | 2100 | | | 21 | [wsc2008qwq](/profile/wsc2008qwq "Candidate Master wsc2008qwq") | 900 | 1000 | 1800 | 2500 | 2600 | | 22 | [starrykiller](/profile/starrykiller "Expert starrykiller") | 900 | 1400 | 1700 | 1900 | | | 23 | [rui_er](/profile/rui_er "International Grandmaster rui_er") | 800 | 1000 | 1600 | 2100 | 2500 | | 24 | [Jryno1](/profile/Jryno1 "Candidate Master Jryno1") | 800 | 1200 | 1600 | 2100 | 2700 | | 25 | [StarSilk](/profile/StarSilk "International Grandmaster StarSilk") | 800 | 1200 | 1600 | 2000 | 2500 | 3000 | 26 | [Rebex](/profile/Rebex "Candidate Master Rebex") | 1000 | 1300 | 1800 | 2000 | | | 27 | [FengLing](/profile/FengLing "Master FengLing") | 800 | 1100 | 1400 | 2200 | | | 28 29 | | A | B | C | D | E | F | 30 | --- | --- | --- | --- | --- | --- | --- | 31 | Average | 857 | 1236 | 1640 | 2029 | 2438 | 2833 | 32 | Actual | 800 | 1300 | 1800 | 2400 | 2600 | 3000 | 33 34 [1981A - Turtle and Piggy Are Playing a Game](/contest/1981/problem/A "Codeforces Round 949 (Div. 2)") 35 36 Idea: [zltzlt](/profile/zltzlt "Grandmaster zltzlt") 37 38 **Hint 1** 39 40 What is Piggy's optimal strategy? 41 42 **Hint 2** 43 44 What does $2l \le r$ mean? 45 46 **Solution** 47 48 Tutorial is loading... 49 50 **Code** 51 52 ``` 53 #include <bits/stdc++.h> 54 using namespace std; 55 56 int main() { 57 int T; 58 scanf("%d", &T); 59 while (T--) { 60 int l, r; 61 scanf("%d%d", &l, &r); 62 printf("%d\n", __lg(r)); 63 } 64 return 0; 65 } 66 ``` 67 68 [1981B - Turtle and an Infinite Sequence](/contest/1981/problem/B "Codeforces Round 949 (Div. 2)") 69 70 Idea: [zltzlt](/profile/zltzlt "Grandmaster zltzlt") 71 72 **Hint 1** 73 74 Consider each bit separately. 75 76 **Hint 2** 77 78 Calculate the time when the $d$-th bit of $a_n$ becomes $1$. 79 80 **Solution 1** 81 82 Tutorial is loading... 83 84 **Solution 2** 85 86 The answer is the bitwise OR of the range $[\max(0, n - m), n + m]$. Let's figure out how to calculate the bitwise OR of the range $[l, r]$. 87 88 We can consider each bit separately. If the $d$-th bit of $l$ is $1$ or the $d$-th bit of $r$ is $1$, then the $d$-th bit of the answer is $1$. 89 90 Otherwise, if $\left\lfloor\frac{l}{2^{d + 1}}\right\rfloor \ne \left\lfloor\frac{r}{2^{d + 1}}\right\rfloor$, then the $d$-th bit has been flipped at least twice from $l$ to $r$, so in this case the $d$-th bit of the answer is also $1$. 91 92 Time complexity: $O(\log (n + m))$ per test case. 93 94 **Code for Solution 1** 95 96 ``` 97 #include <bits/stdc++.h> 98 #define pb emplace_back 99 #define fst first 100 #define scd second 101 #define mkp make_pair 102 #define mems(a, x) memset((a), (x), sizeof(a)) 103 104 using namespace std; 105 typedef long long ll; 106 typedef double db; 107 typedef unsigned long long ull; 108 typedef long double ldb; 109 typedef pair<ll, ll> pii; 110 111 void solve() { 112 ll n, m; 113 scanf("%lld%lld", &n, &m); 114 ll ans = 0; 115 for (int i = 0; i <= 30; ++i) { 116 ll x = n & ((1LL << (i + 1)) - 1); 117 ll t = (1LL << i) - x; 118 if (n >= (1LL << i)) { 119 t = min(t, x + 1); 120 } 121 if (x >= (1LL << i) || t <= m) { 122 ans |= (1LL << i); 123 } 124 } 125 printf("%lld\n", ans); 126 } 127 128 int main() { 129 int T = 1; 130 scanf("%d", &T); 131 while (T--) { 132 solve(); 133 } 134 return 0; 135 } 136 ``` 137 138 **Code for Solution 2** 139 140 ``` 141 #include <bits/stdc++.h> 142 #define pb emplace_back 143 #define fst first 144 #define scd second 145 #define mkp make_pair 146 #define mems(a, x) memset((a), (x), sizeof(a)) 147 148 using namespace std; 149 typedef long long ll; 150 typedef double db; 151 typedef unsigned long long ull; 152 typedef long double ldb; 153 typedef pair<ll, ll> pii; 154 155 void solve() { 156 ll n, m; 157 scanf("%lld%lld", &n, &m); 158 ll l = max(0LL, n - m), r = n + m, ans = 0; 159 for (int i = 31; ~i; --i) { 160 if ((l & (1LL << i)) || (r & (1LL << i)) || (l >> (i + 1)) != (r >> (i + 1))) { 161 ans |= (1LL << i); 162 } 163 } 164 printf("%lld\n", ans); 165 } 166 167 int main() { 168 int T = 1; 169 scanf("%d", &T); 170 while (T--) { 171 solve(); 172 } 173 return 0; 174 } 175 ``` 176 177 [1981C - Turtle and an Incomplete Sequence](/contest/1981/problem/C "Codeforces Round 949 (Div. 2)") 178 179 Idea: [zltzlt](/profile/zltzlt "Grandmaster zltzlt") 180 181 **Hint 1** 182 183 Figure out the case where $a'_1 \ne -1, a'_n \ne -1$ and $a'_2 = a'_3 = \cdots = a'_{n - 1} = -1$ first. 184 185 **Hint 2** 186 187 Imagine a full binary tree. Consider the sequence as a walk on the full binary tree. 188 189 **Solution** 190 191 Tutorial is loading... 192 193 **Code** 194 195 ``` 196 #include <bits/stdc++.h> 197 #define pb emplace_back 198 #define fst first 199 #define scd second 200 #define mkp make_pair 201 #define mems(a, x) memset((a), (x), sizeof(a)) 202 203 using namespace std; 204 typedef long long ll; 205 typedef double db; 206 typedef unsigned long long ull; 207 typedef long double ldb; 208 typedef pair<ll, ll> pii; 209 210 const int maxn = 200100; 211 212 int n, a[maxn]; 213 214 inline vector<int> path(int x, int y) { 215 vector<int> L, R; 216 while (__lg(x) > __lg(y)) { 217 L.pb(x); 218 x >>= 1; 219 } 220 while (__lg(y) > __lg(x)) { 221 R.pb(y); 222 y >>= 1; 223 } 224 while (x != y) { 225 L.pb(x); 226 R.pb(y); 227 x >>= 1; 228 y >>= 1; 229 } 230 L.pb(x); 231 reverse(R.begin(), R.end()); 232 for (int x : R) { 233 L.pb(x); 234 } 235 return L; 236 } 237 238 void solve() { 239 scanf("%d", &n); 240 int l = -1, r = -1; 241 vector<int> vc; 242 for (int i = 1; i <= n; ++i) { 243 scanf("%d", &a[i]); 244 if (a[i] != -1) { 245 if (l == -1) { 246 l = i; 247 } 248 r = i; 249 vc.pb(i); 250 } 251 } 252 if (l == -1) { 253 for (int i = 1; i <= n; ++i) { 254 printf("%d%c", (i & 1) + 1, " \n"[i == n]); 255 } 256 return; 257 } 258 for (int i = l - 1; i; --i) { 259 a[i] = (((l - i) & 1) ? a[l] * 2 : a[l]); 260 } 261 for (int i = r + 1; i <= n; ++i) { 262 a[i] = (((i - r) & 1) ? a[r] * 2 : a[r]); 263 } 264 for (int _ = 1; _ < (int)vc.size(); ++_) { 265 int l = vc[_ - 1], r = vc[_]; 266 vector<int> p = path(a[l], a[r]); 267 if (((int)p.size() & 1) != ((r - l + 1) & 1) || r - l + 1 < (int)p.size()) { 268 puts("-1"); 269 return; 270 } 271 for (int i = 0; i < (int)p.size(); ++i) { 272 a[l + i] = p[i]; 273 } 274 for (int i = l + (int)p.size(), o = 1; i <= r; ++i, o ^= 1) { 275 a[i] = (o ? a[i - 1] * 2 : a[i - 1] / 2); 276 } 277 } 278 for (int i = 1; i <= n; ++i) { 279 printf("%d%c", a[i], " \n"[i == n]); 280 } 281 } 282 283 int main() { 284 int T = 1; 285 scanf("%d", &T); 286 while (T--) { 287 solve(); 288 } 289 return 0; 290 } 291 ``` 292 293 [1981D - Turtle and Multiplication](/contest/1981/problem/D "Codeforces Round 949 (Div. 2)") 294 295 Idea: [sinsop90](/profile/sinsop90 "Candidate Master sinsop90") 296 297 **Hint 1** 298 299 $a_i$ should take different primes. 300 301 **Hint 2** 302 303 Transform it into a graph problem. 304 305 **Solution** 306 307 Tutorial is loading... 308 309 **Code** 310 311 ``` 312 #include <bits/stdc++.h> 313 #define pb emplace_back 314 #define fst first 315 #define scd second 316 #define mkp make_pair 317 #define mems(a, x) memset((a), (x), sizeof(a)) 318 319 using namespace std; 320 typedef long long ll; 321 typedef double db; 322 typedef unsigned long long ull; 323 typedef long double ldb; 324 typedef pair<int, int> pii; 325 326 const int maxn = 4000100; 327 const int N = 1000000; 328 329 int n, a[maxn], pr[maxn], tot, stk[maxn], top; 330 bool vis[maxn]; 331 332 inline void init() { 333 for (int i = 2; i <= N; ++i) { 334 if (!vis[i]) { 335 pr[++tot] = i; 336 } 337 for (int j = 1; j <= tot && i * pr[j] <= N; ++j) { 338 vis[i * pr[j]] = 1; 339 if (i % pr[j] == 0) { 340 break; 341 } 342 } 343 } 344 mems(vis, 0); 345 } 346 347 inline bool check(int x) { 348 if (x & 1) { 349 return x + 1 + x * (x - 1) / 2 >= n; 350 } else { 351 return x * (x - 1) / 2 - x / 2 + 2 + x >= n; 352 } 353 } 354 355 vector<pii> G[10000]; 356 357 void dfs(int u) { 358 while (G[u].size()) { 359 pii p = G[u].back(); 360 G[u].pop_back(); 361 if (vis[p.scd]) { 362 continue; 363 } 364 vis[p.scd] = 1; 365 dfs(p.fst); 366 } 367 stk[++top] = pr[u]; 368 } 369 370 void solve() { 371 scanf("%d", &n); 372 int l = 1, r = 10000, ans = -1; 373 while (l <= r) { 374 int mid = (l + r) >> 1; 375 if (check(mid)) { 376 ans = mid; 377 r = mid - 1; 378 } else { 379 l = mid + 1; 380 } 381 } 382 for (int i = 1; i <= ans; ++i) { 383 vector<pii>().swap(G[i]); 384 } 385 int tot = 0; 386 for (int i = 1; i <= ans; ++i) { 387 for (int j = i; j <= ans; ++j) { 388 if (ans % 2 == 0 && i % 2 == 0 && i + 1 == j) { 389 continue; 390 } 391 G[i].pb(j, ++tot); 392 G[j].pb(i, tot); 393 } 394 } 395 for (int i = 1; i <= tot; ++i) { 396 vis[i] = 0; 397 } 398 top = 0; 399 dfs(1); 400 reverse(stk + 1, stk + top + 1); 401 for (int i = 1; i <= n; ++i) { 402 printf("%d%c", stk[i], " \n"[i == n]); 403 } 404 } 405 406 int main() { 407 init(); 408 int T = 1; 409 scanf("%d", &T); 410 while (T--) { 411 solve(); 412 } 413 return 0; 414 } 415 ``` 416 417 [1981E - Turtle and Intersected Segments](/contest/1981/problem/E "Codeforces Round 949 (Div. 2)") 418 419 Idea: [zltzlt](/profile/zltzlt "Grandmaster zltzlt") 420 Developed by [244mhq](/profile/244mhq "Legendary Grandmaster 244mhq"). 421 422 **Hint 1** 423 424 Stop thinking about Boruvka. 425 426 **Hint 2** 427 428 Most of the edges in the graph are useless. 429 430 **Solution** 431 432 Tutorial is loading... 433 434 **Code** 435 436 ``` 437 #include <bits/stdc++.h> 438 #define pb emplace_back 439 #define fst first 440 #define scd second 441 #define mkp make_pair 442 #define mems(a, x) memset((a), (x), sizeof(a)) 443 444 using namespace std; 445 typedef long long ll; 446 typedef double db; 447 typedef unsigned long long ull; 448 typedef long double ldb; 449 typedef pair<int, int> pii; 450 451 const int maxn = 1000100; 452 453 int n, lsh[maxn], tot, fa[maxn]; 454 pii b[maxn]; 455 456 struct node { 457 int l, r, x; 458 } a[maxn]; 459 460 struct edg { 461 int u, v, d; 462 edg(int a = 0, int b = 0, int c = 0) : u(a), v(b), d(c) {} 463 } E[maxn]; 464 465 int find(int x) { 466 return fa[x] == x ? x : fa[x] = find(fa[x]); 467 } 468 469 inline bool merge(int x, int y) { 470 x = find(x); 471 y = find(y); 472 if (x != y) { 473 fa[x] = y; 474 return 1; 475 } else { 476 return 0; 477 } 478 } 479 480 void solve() { 481 tot = 0; 482 cin >> n; 483 for (int i = 1; i <= n; ++i) { 484 cin >> a[i].l >> a[i].r >> a[i].x; 485 lsh[++tot] = a[i].l; 486 lsh[++tot] = (++a[i].r); 487 } 488 int m = 0; 489 sort(lsh + 1, lsh + tot + 1); 490 tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1; 491 for (int i = 1; i <= n; ++i) { 492 a[i].l = lower_bound(lsh + 1, lsh + tot + 1, a[i].l) - lsh; 493 a[i].r = lower_bound(lsh + 1, lsh + tot + 1, a[i].r) - lsh; 494 b[++m] = mkp(a[i].l, i); 495 b[++m] = mkp(a[i].r, -i); 496 } 497 set<pii> S; 498 sort(b + 1, b + m + 1); 499 int tt = 0; 500 for (int i = 1; i <= m; ++i) { 501 int j = b[i].scd; 502 if (j > 0) { 503 auto it = S.insert(mkp(a[j].x, j)).fst; 504 if (it != S.begin()) { 505 int k = prev(it)->scd; 506 E[++tt] = edg(j, k, abs(a[j].x - a[k].x)); 507 } 508 if (next(it) != S.end()) { 509 int k = next(it)->scd; 510 E[++tt] = edg(j, k, abs(a[j].x - a[k].x)); 511 } 512 } else { 513 j = -j; 514 S.erase(mkp(a[j].x, j)); 515 } 516 } 517 for (int i = 1; i <= n; ++i) { 518 fa[i] = i; 519 } 520 sort(E + 1, E + tt + 1, [&](const edg &a, const edg &b) { 521 return a.d < b.d; 522 }); 523 ll ans = 0, cnt = 0; 524 for (int i = 1; i <= tt; ++i) { 525 if (merge(E[i].u, E[i].v)) { 526 ++cnt; 527 ans += E[i].d; 528 } 529 } 530 cout << (cnt == n - 1 ? ans : -1) << '\n'; 531 } 532 533 int main() { 534 ios::sync_with_stdio(0); 535 cin.tie(0); 536 cout.tie(0); 537 int T = 1; 538 cin >> T; 539 while (T--) { 540 solve(); 541 } 542 return 0; 543 } 544 ``` 545 546 [1981F - Turtle and Paths on a Tree](/contest/1981/problem/F "Codeforces Round 949 (Div. 2)") 547 548 Idea: [yinhee](/profile/yinhee "Candidate Master yinhee") 549 Developed by [244mhq](/profile/244mhq "Legendary Grandmaster 244mhq") and [zltzlt](/profile/zltzlt "Grandmaster zltzlt"). 550 Thanks [AFewSuns](/profile/AFewSuns "Grandmaster AFewSuns") and [crazy_sea](/profile/crazy_sea "Legendary Grandmaster crazy_sea") for discovering Solution 2, which runs faster than Solution 1! 551 552 **Hint 1** 553 554 Try some dp that takes $O(n^2)$ time. 555 556 **Hint 2** 557 558 What's the maximum MEX in the optimal good set of paths? 559 560 **Solution 1** 561 562 Tutorial is loading... 563 564 **Solution 2** 565 566 Read the $O(n^2)$ part of Solution 1 first. 567 568 Consider using a segment tree to maintain the dp values. The transitions for $u$ with at most one child are easy to maintain, so we only need to consider the case with two children. 569 570 First, use a segment tree to maintain the minimum value of $f_{u,i} + i$, so $\text{minx}$ and $\text{miny}$ can be computed. The value of $f_{u,a_u}$ can be set to $+\infty$ by a point update. 571 572 Ignoring how to compute $k$ for now, in the end, all $f_{x,i}$ are incremented by $\text{miny}$, all $f_{y,i}$ are incremented by $\text{minx}$, and the segment trees are merged. Finally, all $f_{u,i}$ are taken as the minimum with $k$. 573 574 To compute $k$, which is $\min\limits_{i \neq a_u} (f_{x,i} + f_{y,i} + i)$, we can use a similar segment tree merging method, quickly computing this as we recursively descend to the leaf nodes of the segment tree. Additionally, we need to maintain the minimum value of $f_{u,i}$. 575 576 Time complexity: $\mathcal{O}(n \log n)$ per test case. 577 578 **Code for Solution 1** 579 580 ``` 581 #include <bits/stdc++.h> 582 #define pb emplace_back 583 #define fst first 584 #define scd second 585 #define mkp make_pair 586 #define mems(a, x) memset((a), (x), sizeof(a)) 587 588 using namespace std; 589 typedef long long ll; 590 typedef double db; 591 typedef unsigned long long ull; 592 typedef long double ldb; 593 typedef pair<ll, ll> pii; 594 595 const int maxn = 25050; 596 const int inf = 0x3f3f3f3f; 597 598 int n, m, a[maxn], f[maxn][4000]; 599 vector<int> G[maxn]; 600 601 void dfs(int u) { 602 if (G[u].empty()) { 603 for (int i = 1; i <= m; ++i) { 604 f[u][i] = (i == a[u] ? inf : 0); 605 } 606 return; 607 } 608 if ((int)G[u].size() == 1) { 609 int x = G[u][0]; 610 dfs(x); 611 int mn = inf; 612 for (int i = 1; i <= m; ++i) { 613 if (i != a[u]) { 614 mn = min(mn, f[x][i] + i); 615 } 616 } 617 if (u == 1) { 618 printf("%d\n", mn); 619 return; 620 } 621 for (int i = 1; i <= m; ++i) { 622 f[u][i] = (i == a[u] ? inf : min(f[x][i], mn)); 623 } 624 return; 625 } 626 int x = G[u][0], y = G[u][1], mnx = inf, mny = inf, k = inf; 627 dfs(x); 628 dfs(y); 629 for (int i = 1; i <= m; ++i) { 630 if (i != a[u]) { 631 mnx = min(mnx, f[x][i] + i); 632 mny = min(mny, f[y][i] + i); 633 k = min(k, f[x][i] + f[y][i] + i); 634 } 635 } 636 k = min(k, mnx + mny); 637 if (u == 1) { 638 printf("%d\n", k); 639 return; 640 } 641 for (int i = 1; i <= m; ++i) { 642 f[u][i] = (i == a[u] ? inf : min({f[x][i] + mny, f[y][i] + mnx, k})); 643 } 644 } 645 646 void solve() { 647 scanf("%d", &n); 648 m = min(n + 1, 3863); 649 for (int i = 1; i <= n; ++i) { 650 scanf("%d", &a[i]); 651 vector<int>().swap(G[i]); 652 } 653 for (int i = 2, p; i <= n; ++i) { 654 scanf("%d", &p); 655 G[p].pb(i); 656 } 657 dfs(1); 658 } 659 660 int main() { 661 int T = 1; 662 scanf("%d", &T); 663 while (T--) { 664 solve(); 665 } 666 return 0; 667 } 668 ``` 669 670 **Code for Solution 2** 671 672 ``` 673 #include<bits/stdc++.h> 674 using namespace std; 675 namespace my_std{ 676 #define ll long long 677 #define bl bool 678 ll my_pow(ll a,ll b,ll mod){ 679 ll res=1; 680 if(!b) return 1; 681 while(b){ 682 if(b&1) res=(res*a)%mod; 683 a=(a*a)%mod; 684 b>>=1; 685 } 686 return res; 687 } 688 ll qpow(ll a,ll b){ 689 ll res=1; 690 if(!b) return 1; 691 while(b){ 692 if(b&1) res*=a; 693 a*=a; 694 b>>=1; 695 } 696 return res; 697 } 698 #define db double 699 #define pf printf 700 #define pc putchar 701 #define fr(i,x,y) for(register ll i=(x);i<=(y);i++) 702 #define pfr(i,x,y) for(register ll i=(x);i>=(y);i--) 703 #define go(u) for(ll i=head[u];i;i=e[i].nxt) 704 #define enter pc('\n') 705 #define space pc(' ') 706 #define fir first 707 #define sec second 708 #define MP make_pair 709 #define il inline 710 #define inf 1e18 711 #define random(x) rand()*rand()%(x) 712 #define inv(a,mod) my_pow((a),(mod-2),(mod)) 713 il ll read(){ 714 ll sum=0,f=1; 715 char ch=0; 716 while(!isdigit(ch)){ 717 if(ch=='-') f=-1; 718 ch=getchar(); 719 } 720 while(isdigit(ch)){ 721 sum=sum*10+(ch^48); 722 ch=getchar(); 723 } 724 return sum*f; 725 } 726 il void write(ll x){ 727 if(x<0){ 728 x=-x; 729 pc('-'); 730 } 731 if(x>9) write(x/10); 732 pc(x%10+'0'); 733 } 734 il void writeln(ll x){ 735 write(x); 736 enter; 737 } 738 il void writesp(ll x){ 739 write(x); 740 space; 741 } 742 } 743 using namespace my_std; 744 #define LC tree[x].lc 745 #define RC tree[x].rc 746 ll t,n,a[25025],ch[25025][2],ans=inf; 747 ll rt[25025],tot=0; 748 struct node{ 749 ll minn1,minn2,lz,lzmin,lc,rc; 750 il void addtag(ll v,ll vmin,ll l){ 751 minn1=min(minn1+v,vmin); 752 minn2=min(minn2+v,vmin+l); 753 lz+=v; 754 lzmin=min(lzmin+v,vmin); 755 } 756 }tree[1000010]; 757 il void pushup(ll x){ 758 tree[x].minn1=min(tree[LC].minn1,tree[RC].minn1); 759 tree[x].minn2=min(tree[LC].minn2,tree[RC].minn2); 760 } 761 il ll newnode(){ 762 tree[++tot]=(node){(ll)inf,(ll)inf,0,(ll)inf,0,0}; 763 return tot; 764 } 765 il void pushdown(ll x,ll l,ll r){ 766 if(!LC) LC=newnode(); 767 if(!RC) RC=newnode(); 768 ll mid=(l+r)>>1; 769 tree[LC].addtag(tree[x].lz,tree[x].lzmin,l); 770 tree[RC].addtag(tree[x].lz,tree[x].lzmin,mid+1); 771 tree[x].lz=0; 772 tree[x].lzmin=inf; 773 } 774 void upd(ll &x,ll l,ll r,ll pos){ 775 if(!x) x=newnode(); 776 if(l==r){ 777 tree[x].minn1=tree[x].minn2=inf; 778 return; 779 } 780 ll mid=(l+r)>>1; 781 pushdown(x,l,r); 782 if(pos<=mid) upd(LC,l,mid,pos); 783 else upd(RC,mid+1,r,pos); 784 pushup(x); 785 } 786 void add(ll &x,ll l,ll r,ll ql,ll qr,ll v){ 787 if(!x) x=newnode(); 788 if(ql<=l&&r<=qr){ 789 tree[x].addtag(v,(ll)inf,l); 790 return; 791 } 792 ll mid=(l+r)>>1; 793 pushdown(x,l,r); 794 if(ql<=mid) add(LC,l,mid,ql,qr,v); 795 if(mid<qr) add(RC,mid+1,r,ql,qr,v); 796 pushup(x); 797 } 798 void mdf(ll &x,ll l,ll r,ll ql,ll qr,ll v){ 799 if(!x) x=newnode(); 800 if(ql<=l&&r<=qr){ 801 tree[x].addtag(0,v,l); 802 return; 803 } 804 ll mid=(l+r)>>1; 805 pushdown(x,l,r); 806 if(ql<=mid) mdf(LC,l,mid,ql,qr,v); 807 if(mid<qr) mdf(RC,mid+1,r,ql,qr,v); 808 pushup(x); 809 } 810 ll merge(ll x,ll y,ll l,ll r){ 811 if(!LC&&!RC){ 812 tree[y].addtag(0,tree[x].minn1,l); 813 return y; 814 } 815 if(!tree[y].lc&&!tree[y].rc){ 816 tree[x].addtag(0,tree[y].minn1,l); 817 return x; 818 } 819 ll mid=(l+r)>>1; 820 pushdown(x,l,r); 821 pushdown(y,l,r); 822 LC=merge(LC,tree[y].lc,l,mid); 823 RC=merge(RC,tree[y].rc,mid+1,r); 824 pushup(x); 825 return x; 826 } 827 ll query(ll x,ll y,ll l,ll r){ 828 if(!LC&&!RC) return tree[x].minn1+tree[y].minn2; 829 if(!tree[y].lc&&!tree[y].rc) return tree[y].minn1+tree[x].minn2; 830 ll mid=(l+r)>>1,res=inf; 831 pushdown(x,l,r); 832 pushdown(y,l,r); 833 res=min(res,query(LC,tree[y].lc,l,mid)); 834 res=min(res,query(RC,tree[y].rc,mid+1,r)); 835 return res; 836 } 837 void dfs(ll u){ 838 if(!ch[u][0]){ 839 mdf(rt[u],1,n+1,1,n+1,0); 840 if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]); 841 if(u==1) ans=0; 842 } 843 else if(!ch[u][1]){ 844 dfs(ch[u][0]); 845 rt[u]=rt[ch[u][0]]; 846 if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]); 847 ll minn=tree[rt[u]].minn2; 848 mdf(rt[u],1,n+1,1,n+1,minn); 849 if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]); 850 if(u==1) ans=minn; 851 } 852 else{ 853 ll x=ch[u][0],y=ch[u][1]; 854 dfs(x); 855 dfs(y); 856 if(a[u]<=(n+1)){ 857 upd(rt[x],1,n+1,a[u]); 858 upd(rt[y],1,n+1,a[u]); 859 } 860 ll minx=tree[rt[x]].minn2,miny=tree[rt[y]].minn2,k=min(query(rt[x],rt[y],1,n+1),minx+miny); 861 add(rt[x],1,n+1,1,n+1,miny); 862 add(rt[y],1,n+1,1,n+1,minx); 863 rt[u]=merge(rt[x],rt[y],1,n+1); 864 mdf(rt[u],1,n+1,1,n+1,k); 865 if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]); 866 if(u==1) ans=k; 867 } 868 } 869 il void clr(){ 870 fr(i,1,n) ch[i][0]=ch[i][1]=rt[i]=0; 871 tot=0; 872 ans=inf; 873 } 874 int main(){ 875 t=read(); 876 while(t--){ 877 n=read(); 878 fr(i,1,n) a[i]=read(); 879 fr(i,2,n){ 880 ll x=read(); 881 if(!ch[x][0]) ch[x][0]=i; 882 else ch[x][1]=i; 883 } 884 dfs(1); 885 writeln(ans); 886 clr(); 887 } 888 } 889 /* 890 1 891 5 892 3 2 2 1 1 893 1 1 2 2 894 ans: 895 4 896 */ 897 ```