codeforces-scrape

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

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 ```