Thank you for participating! Sorry for being much harder than usual Div. 2 :( But we still hope you find some of our problems interesting.↵
↵
<spoiler summary="Rating predictions (Inspired by sum's editorial)">↵
It seems like a joke now...↵
↵
| Person | A | B | C | D | E | F |↵
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |↵
| [user: zltzlt, 2024-5-31] | 800 | 1400 | 1600 | 2000 | 2300 | 2800 |↵
| [user: small_peter, 2024-5-31] | 800 | 1400 | 1700 | 1600 | | |↵
| [user: WRuperD, 2024-5-31] | 800 | 1300 | 1600 | 2000 | | 2800 |↵
| [user: yinhee, 2024-5-31] | 800 | 1000 | 1500 | 2100 | 2200 | 2700 |↵
| [user: sinsop90, 2024-5-31] | 1000 | 1300 | 1500 | 2000 | 2200 | |↵
| [user: Yujiahe,2024-05-28] | 800 | 1100 | 1600 | 1900 | | 2700 |↵
| [user: CharlieV, 2024-5-31] | | | | 2400 | 2500 | 3000 |↵
| [user: JWRuixi, 2024-5-31] | | | | 1800 | | |↵
| [user: Edwin__VanCleef, 2024-5-31] | | | 1600 | 1800 | |↵
| [user: QwQwf, 2024-5-31] | 1000 | 1600 | 2000 | 2100 | | |↵
| [user: wsc2008qwq, 2024-5-31] | 900 | 1000 | 1800 | 2500 | 2600 | |↵
| [user: starrykiller, 2024-5-31] | 900 | 1400 | 1700 | 1900 | | |↵
| [user: rui_er, 2024-5-31] | 800 | 1000 | 1600 | 2100 | 2500 | |↵
| [user: Jryno1, 2024-5-31] | 800 | 1200 | 1600 | 2100 | 2700 | |↵
| [user: StarSilk, 2024-5-31] | 800 | 1200 | 1600 | 2000 | 2500 | 3000 |↵
| [user: lovely-ckj, 2024-5-31] | 1000 | 1300 | 1800 | 2000 | | |↵
| [user: FengLing, 2024-5-31] | 800 | 1100 | 1400 | 2200 | | |↵
↵
| | A | B | C | D | E | F |↵
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |↵
| Average | 857 | 1236 | 1640 | 2029 | 2438 | 2833 |↵
| Actual | | | | | | |↵
</spoiler>↵
↵
[problem: 1981A]↵
↵
Idea: [user: zltzlt, 2024-5-31]↵
↵
<spoiler summary="Hint 1">↵
What is Piggy's optimal strategy?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What does $2l \le r$ mean?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1981A]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
int T;↵
scanf("%d", &T);↵
while (T--) {↵
int l, r;↵
scanf("%d%d", &l, &r);↵
printf("%d\n", __lg(r));↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem: 1981B]↵
↵
Idea: [user: zltzlt, 2024-5-31]↵
↵
<spoiler summary="Hint 1">↵
Consider each bit separately.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Calculate the time when the $d$-th bit of $a_n$ becomes $1$.↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
[tutorial:1981B]↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
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]$.↵
↵
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$.↵
↵
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$.↵
↵
Time complexity: $O(\log (n + m))$ per test case.↵
</spoiler>↵
↵
<spoiler summary="Code for Solution 1">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define pb emplace_back↵
#define fst first↵
#define scd second↵
#define mkp make_pair↵
#define mems(a, x) memset((a), (x), sizeof(a))↵
↵
using namespace std;↵
typedef long long ll;↵
typedef double db;↵
typedef unsigned long long ull;↵
typedef long double ldb;↵
typedef pair<ll, ll> pii;↵
↵
void solve() {↵
ll n, m;↵
scanf("%lld%lld", &n, &m);↵
ll ans = 0;↵
for (int i = 0; i <= 30; ++i) {↵
ll x = n & ((1LL << (i + 1)) - 1);↵
ll t = (1LL << i) - x;↵
if (n >= (1LL << i)) {↵
t = min(t, x + 1);↵
}↵
if (x >= (1LL << i) || t <= m) {↵
ans |= (1LL << i);↵
}↵
}↵
printf("%lld\n", ans);↵
}↵
↵
int main() {↵
int T = 1;↵
scanf("%d", &T);↵
while (T--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Code for Solution 2">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define pb emplace_back↵
#define fst first↵
#define scd second↵
#define mkp make_pair↵
#define mems(a, x) memset((a), (x), sizeof(a))↵
↵
using namespace std;↵
typedef long long ll;↵
typedef double db;↵
typedef unsigned long long ull;↵
typedef long double ldb;↵
typedef pair<ll, ll> pii;↵
↵
void solve() {↵
ll n, m;↵
scanf("%lld%lld", &n, &m);↵
ll l = max(0LL, n - m), r = n + m, ans = 0;↵
for (int i = 31; ~i; --i) {↵
if ((l & (1LL << i)) || (r & (1LL << i)) || (l >> (i + 1)) != (r >> (i + 1))) {↵
ans |= (1LL << i);↵
}↵
}↵
printf("%lld\n", ans);↵
}↵
↵
int main() {↵
int T = 1;↵
scanf("%d", &T);↵
while (T--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem: 1981C]↵
↵
Idea: [user: zltzlt, 2024-5-31]↵
↵
<spoiler summary="Hint 1">↵
Figure out the case where $a'_1 \ne -1, a'_n \ne -1$ and $a'_2 = a'_3 = \cdots = a'_{n - 1} = -1$ first.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Imagine a full binary tree. Consider the sequence as a walk on the full binary tree.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1981C]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define pb emplace_back↵
#define fst first↵
#define scd second↵
#define mkp make_pair↵
#define mems(a, x) memset((a), (x), sizeof(a))↵
↵
using namespace std;↵
typedef long long ll;↵
typedef double db;↵
typedef unsigned long long ull;↵
typedef long double ldb;↵
typedef pair<ll, ll> pii;↵
↵
const int maxn = 200100;↵
↵
int n, a[maxn];↵
↵
inline vector<int> path(int x, int y) {↵
vector<int> L, R;↵
while (__lg(x) > __lg(y)) {↵
L.pb(x);↵
x >>= 1;↵
}↵
while (__lg(y) > __lg(x)) {↵
R.pb(y);↵
y >>= 1;↵
}↵
while (x != y) {↵
L.pb(x);↵
R.pb(y);↵
x >>= 1;↵
y >>= 1;↵
}↵
L.pb(x);↵
reverse(R.begin(), R.end());↵
for (int x : R) {↵
L.pb(x);↵
}↵
return L;↵
}↵
↵
void solve() {↵
scanf("%d", &n);↵
int l = -1, r = -1;↵
vector<int> vc;↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &a[i]);↵
if (a[i] != -1) {↵
if (l == -1) {↵
l = i;↵
}↵
r = i;↵
vc.pb(i);↵
}↵
}↵
if (l == -1) {↵
for (int i = 1; i <= n; ++i) {↵
printf("%d%c", (i & 1) + 1, " \n"[i == n]);↵
}↵
return;↵
}↵
for (int i = l - 1; i; --i) {↵
a[i] = (((l - i) & 1) ? a[l] * 2 : a[l]);↵
}↵
for (int i = r + 1; i <= n; ++i) {↵
a[i] = (((i - r) & 1) ? a[r] * 2 : a[r]);↵
}↵
for (int _ = 1; _ < (int)vc.size(); ++_) {↵
int l = vc[_ - 1], r = vc[_];↵
vector<int> p = path(a[l], a[r]);↵
if (((int)p.size() & 1) != ((r - l + 1) & 1) || r - l + 1 < (int)p.size()) {↵
puts("-1");↵
return;↵
}↵
for (int i = 0; i < (int)p.size(); ++i) {↵
a[l + i] = p[i];↵
}↵
for (int i = l + (int)p.size(), o = 1; i <= r; ++i, o ^= 1) {↵
a[i] = (o ? a[i - 1] * 2 : a[i - 1] / 2);↵
}↵
}↵
for (int i = 1; i <= n; ++i) {↵
printf("%d%c", a[i], " \n"[i == n]);↵
}↵
}↵
↵
int main() {↵
int T = 1;↵
scanf("%d", &T);↵
while (T--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem: 1981D]↵
↵
Idea: [user: sinsop90, 2024-5-31]↵
↵
<spoiler summary="Hint 1">↵
$a_i$ should take different primes.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Transform it into a graph problem.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1981D]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define pb emplace_back↵
#define fst first↵
#define scd second↵
#define mkp make_pair↵
#define mems(a, x) memset((a), (x), sizeof(a))↵
↵
using namespace std;↵
typedef long long ll;↵
typedef double db;↵
typedef unsigned long long ull;↵
typedef long double ldb;↵
typedef pair<int, int> pii;↵
↵
const int maxn = 4000100;↵
const int N = 1000000;↵
↵
int n, a[maxn], pr[maxn], tot, stk[maxn], top;↵
bool vis[maxn];↵
↵
inline void init() {↵
for (int i = 2; i <= N; ++i) {↵
if (!vis[i]) {↵
pr[++tot] = i;↵
}↵
for (int j = 1; j <= tot && i * pr[j] <= N; ++j) {↵
vis[i * pr[j]] = 1;↵
if (i % pr[j] == 0) {↵
break;↵
}↵
}↵
}↵
mems(vis, 0);↵
}↵
↵
inline bool check(int x) {↵
if (x & 1) {↵
return x + 1 + x * (x - 1) / 2 >= n;↵
} else {↵
return x * (x - 1) / 2 - x / 2 + 2 + x >= n;↵
}↵
}↵
↵
vector<pii> G[10000];↵
↵
void dfs(int u) {↵
while (G[u].size()) {↵
pii p = G[u].back();↵
G[u].pop_back();↵
if (vis[p.scd]) {↵
continue;↵
}↵
vis[p.scd] = 1;↵
dfs(p.fst);↵
}↵
stk[++top] = pr[u];↵
}↵
↵
void solve() {↵
scanf("%d", &n);↵
int l = 1, r = 10000, ans = -1;↵
while (l <= r) {↵
int mid = (l + r) >> 1;↵
if (check(mid)) {↵
ans = mid;↵
r = mid - 1;↵
} else {↵
l = mid + 1;↵
}↵
}↵
for (int i = 1; i <= ans; ++i) {↵
vector<pii>().swap(G[i]);↵
}↵
int tot = 0;↵
for (int i = 1; i <= ans; ++i) {↵
for (int j = i; j <= ans; ++j) {↵
if (ans % 2 == 0 && i % 2 == 0 && i + 1 == j) {↵
continue;↵
}↵
G[i].pb(j, ++tot);↵
G[j].pb(i, tot);↵
}↵
}↵
for (int i = 1; i <= tot; ++i) {↵
vis[i] = 0;↵
}↵
top = 0;↵
dfs(1);↵
reverse(stk + 1, stk + top + 1);↵
for (int i = 1; i <= n; ++i) {↵
printf("%d%c", stk[i], " \n"[i == n]);↵
}↵
}↵
↵
int main() {↵
init();↵
int T = 1;↵
scanf("%d", &T);↵
while (T--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem: 1981E]↵
↵
Idea: [user: zltzlt, 2024-5-31]↵
<br>↵
Developed by [user: 244mhq, 2024-5-31].↵
↵
<spoiler summary="Hint 1">↵
Stop thinking about Boruvka.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Most of the edges in the graph are useless.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1981E]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define pb emplace_back↵
#define fst first↵
#define scd second↵
#define mkp make_pair↵
#define mems(a, x) memset((a), (x), sizeof(a))↵
↵
using namespace std;↵
typedef long long ll;↵
typedef double db;↵
typedef unsigned long long ull;↵
typedef long double ldb;↵
typedef pair<int, int> pii;↵
↵
const int maxn = 1000100;↵
↵
int n, lsh[maxn], tot, fa[maxn];↵
pii b[maxn];↵
↵
struct node {↵
int l, r, x;↵
} a[maxn];↵
↵
struct edg {↵
int u, v, d;↵
edg(int a = 0, int b = 0, int c = 0) : u(a), v(b), d(c) {}↵
} E[maxn];↵
↵
int find(int x) {↵
return fa[x] == x ? x : fa[x] = find(fa[x]);↵
}↵
↵
inline bool merge(int x, int y) {↵
x = find(x);↵
y = find(y);↵
if (x != y) {↵
fa[x] = y;↵
return 1;↵
} else {↵
return 0;↵
}↵
}↵
↵
void solve() {↵
tot = 0;↵
cin >> n;↵
for (int i = 1; i <= n; ++i) {↵
cin >> a[i].l >> a[i].r >> a[i].x;↵
lsh[++tot] = a[i].l;↵
lsh[++tot] = (++a[i].r);↵
}↵
int m = 0;↵
sort(lsh + 1, lsh + tot + 1);↵
tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;↵
for (int i = 1; i <= n; ++i) {↵
a[i].l = lower_bound(lsh + 1, lsh + tot + 1, a[i].l) - lsh;↵
a[i].r = lower_bound(lsh + 1, lsh + tot + 1, a[i].r) - lsh;↵
b[++m] = mkp(a[i].l, i);↵
b[++m] = mkp(a[i].r, -i);↵
}↵
set<pii> S;↵
sort(b + 1, b + m + 1);↵
int tt = 0;↵
for (int i = 1; i <= m; ++i) {↵
int j = b[i].scd;↵
if (j > 0) {↵
auto it = S.insert(mkp(a[j].x, j)).fst;↵
if (it != S.begin()) {↵
int k = prev(it)->scd;↵
E[++tt] = edg(j, k, abs(a[j].x - a[k].x));↵
}↵
if (next(it) != S.end()) {↵
int k = next(it)->scd;↵
E[++tt] = edg(j, k, abs(a[j].x - a[k].x));↵
}↵
} else {↵
j = -j;↵
S.erase(mkp(a[j].x, j));↵
}↵
}↵
for (int i = 1; i <= n; ++i) {↵
fa[i] = i;↵
}↵
sort(E + 1, E + tt + 1, [&](const edg &a, const edg &b) {↵
return a.d < b.d;↵
});↵
ll ans = 0, cnt = 0;↵
for (int i = 1; i <= tt; ++i) {↵
if (merge(E[i].u, E[i].v)) {↵
++cnt;↵
ans += E[i].d;↵
}↵
}↵
cout << (cnt == n - 1 ? ans : -1) << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int T = 1;↵
cin >> T;↵
while (T--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem: 1981F]↵
↵
Idea: [user: yinhee, 2024-5-31]↵
<br>↵
Developed by [user: 244mhq, 2024-5-31] and [user: zltzlt, 2024-5-31].↵
<br>↵
Thanks [user: AFewSuns, 2024-5-31] and [user: crazy_sea, 2024-5-31] for discovering Solution 2, which runs faster than Solution 1!↵
↵
<spoiler summary="Hint 1">↵
Try some dp that takes $O(n^2)$ time.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What's the maximum MEX in the optimal good set of paths?↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
[tutorial:1981F]↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
Read the $O(n^2)$ part of Solution 1 first.↵
↵
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.↵
↵
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.↵
↵
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$.↵
↵
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}$.↵
↵
Time complexity: $\mathcal{O}(n \log n)$ per test case.↵
</spoiler>↵
↵
<spoiler summary="Code for Solution 1">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define pb emplace_back↵
#define fst first↵
#define scd second↵
#define mkp make_pair↵
#define mems(a, x) memset((a), (x), sizeof(a))↵
↵
using namespace std;↵
typedef long long ll;↵
typedef double db;↵
typedef unsigned long long ull;↵
typedef long double ldb;↵
typedef pair<ll, ll> pii;↵
↵
const int maxn = 25050;↵
const int inf = 0x3f3f3f3f;↵
↵
int n, m, a[maxn], f[maxn][4000];↵
vector<int> G[maxn];↵
↵
void dfs(int u) {↵
if (G[u].empty()) {↵
for (int i = 1; i <= m; ++i) {↵
f[u][i] = (i == a[u] ? inf : 0);↵
}↵
return;↵
}↵
if ((int)G[u].size() == 1) {↵
int x = G[u][0];↵
dfs(x);↵
int mn = inf;↵
for (int i = 1; i <= m; ++i) {↵
if (i != a[u]) {↵
mn = min(mn, f[x][i] + i);↵
}↵
}↵
if (u == 1) {↵
printf("%d\n", mn);↵
return;↵
}↵
for (int i = 1; i <= m; ++i) {↵
f[u][i] = (i == a[u] ? inf : min(f[x][i], mn));↵
}↵
return;↵
}↵
int x = G[u][0], y = G[u][1], mnx = inf, mny = inf, k = inf;↵
dfs(x);↵
dfs(y);↵
for (int i = 1; i <= m; ++i) {↵
if (i != a[u]) {↵
mnx = min(mnx, f[x][i] + i);↵
mny = min(mny, f[y][i] + i);↵
k = min(k, f[x][i] + f[y][i] + i);↵
}↵
}↵
k = min(k, mnx + mny);↵
if (u == 1) {↵
printf("%d\n", k);↵
return;↵
}↵
for (int i = 1; i <= m; ++i) {↵
f[u][i] = (i == a[u] ? inf : min({f[x][i] + mny, f[y][i] + mnx, k}));↵
}↵
}↵
↵
void solve() {↵
scanf("%d", &n);↵
m = min(n + 1, 3863);↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &a[i]);↵
vector<int>().swap(G[i]);↵
}↵
for (int i = 2, p; i <= n; ++i) {↵
scanf("%d", &p);↵
G[p].pb(i);↵
}↵
dfs(1);↵
}↵
↵
int main() {↵
int T = 1;↵
scanf("%d", &T);↵
while (T--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Code for Solution 2">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
namespace my_std{↵
#define ll long long↵
#define bl bool↵
ll my_pow(ll a,ll b,ll mod){↵
ll res=1;↵
if(!b) return 1;↵
while(b){↵
if(b&1) res=(res*a)%mod;↵
a=(a*a)%mod;↵
b>>=1;↵
}↵
return res;↵
}↵
ll qpow(ll a,ll b){↵
ll res=1;↵
if(!b) return 1;↵
while(b){↵
if(b&1) res*=a;↵
a*=a;↵
b>>=1;↵
}↵
return res;↵
}↵
#define db double↵
#define pf printf↵
#define pc putchar↵
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)↵
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)↵
#define go(u) for(ll i=head[u];i;i=e[i].nxt)↵
#define enter pc('\n')↵
#define space pc(' ')↵
#define fir first↵
#define sec second↵
#define MP make_pair↵
#define il inline↵
#define inf 1e18↵
#define random(x) rand()*rand()%(x)↵
#define inv(a,mod) my_pow((a),(mod-2),(mod))↵
il ll read(){↵
ll sum=0,f=1;↵
char ch=0;↵
while(!isdigit(ch)){↵
if(ch=='-') f=-1;↵
ch=getchar();↵
}↵
while(isdigit(ch)){↵
sum=sum*10+(ch^48);↵
ch=getchar();↵
}↵
return sum*f;↵
}↵
il void write(ll x){↵
if(x<0){↵
x=-x;↵
pc('-');↵
}↵
if(x>9) write(x/10);↵
pc(x%10+'0');↵
}↵
il void writeln(ll x){↵
write(x);↵
enter;↵
}↵
il void writesp(ll x){↵
write(x);↵
space;↵
}↵
}↵
using namespace my_std;↵
#define LC tree[x].lc↵
#define RC tree[x].rc↵
ll t,n,a[25025],ch[25025][2],ans=inf;↵
ll rt[25025],tot=0;↵
struct node{↵
ll minn1,minn2,lz,lzmin,lc,rc;↵
il void addtag(ll v,ll vmin,ll l){↵
minn1=min(minn1+v,vmin);↵
minn2=min(minn2+v,vmin+l);↵
lz+=v;↵
lzmin=min(lzmin+v,vmin);↵
}↵
}tree[1000010];↵
il void pushup(ll x){↵
tree[x].minn1=min(tree[LC].minn1,tree[RC].minn1);↵
tree[x].minn2=min(tree[LC].minn2,tree[RC].minn2);↵
}↵
il ll newnode(){↵
tree[++tot]=(node){(ll)inf,(ll)inf,0,(ll)inf,0,0};↵
return tot;↵
}↵
il void pushdown(ll x,ll l,ll r){↵
if(!LC) LC=newnode();↵
if(!RC) RC=newnode();↵
ll mid=(l+r)>>1;↵
tree[LC].addtag(tree[x].lz,tree[x].lzmin,l);↵
tree[RC].addtag(tree[x].lz,tree[x].lzmin,mid+1);↵
tree[x].lz=0;↵
tree[x].lzmin=inf;↵
}↵
void upd(ll &x,ll l,ll r,ll pos){↵
if(!x) x=newnode();↵
if(l==r){↵
tree[x].minn1=tree[x].minn2=inf;↵
return;↵
}↵
ll mid=(l+r)>>1;↵
pushdown(x,l,r);↵
if(pos<=mid) upd(LC,l,mid,pos);↵
else upd(RC,mid+1,r,pos);↵
pushup(x);↵
}↵
void add(ll &x,ll l,ll r,ll ql,ll qr,ll v){↵
if(!x) x=newnode();↵
if(ql<=l&&r<=qr){↵
tree[x].addtag(v,(ll)inf,l);↵
return;↵
}↵
ll mid=(l+r)>>1;↵
pushdown(x,l,r);↵
if(ql<=mid) add(LC,l,mid,ql,qr,v);↵
if(mid<qr) add(RC,mid+1,r,ql,qr,v);↵
pushup(x);↵
}↵
void mdf(ll &x,ll l,ll r,ll ql,ll qr,ll v){↵
if(!x) x=newnode();↵
if(ql<=l&&r<=qr){↵
tree[x].addtag(0,v,l);↵
return;↵
}↵
ll mid=(l+r)>>1;↵
pushdown(x,l,r);↵
if(ql<=mid) mdf(LC,l,mid,ql,qr,v);↵
if(mid<qr) mdf(RC,mid+1,r,ql,qr,v);↵
pushup(x);↵
}↵
ll merge(ll x,ll y,ll l,ll r){↵
if(!LC&&!RC){↵
tree[y].addtag(0,tree[x].minn1,l);↵
return y;↵
}↵
if(!tree[y].lc&&!tree[y].rc){↵
tree[x].addtag(0,tree[y].minn1,l);↵
return x;↵
}↵
ll mid=(l+r)>>1;↵
pushdown(x,l,r);↵
pushdown(y,l,r);↵
LC=merge(LC,tree[y].lc,l,mid);↵
RC=merge(RC,tree[y].rc,mid+1,r);↵
pushup(x);↵
return x;↵
}↵
ll query(ll x,ll y,ll l,ll r){↵
if(!LC&&!RC) return tree[x].minn1+tree[y].minn2;↵
if(!tree[y].lc&&!tree[y].rc) return tree[y].minn1+tree[x].minn2;↵
ll mid=(l+r)>>1,res=inf;↵
pushdown(x,l,r);↵
pushdown(y,l,r);↵
res=min(res,query(LC,tree[y].lc,l,mid));↵
res=min(res,query(RC,tree[y].rc,mid+1,r));↵
return res;↵
}↵
void dfs(ll u){↵
if(!ch[u][0]){↵
mdf(rt[u],1,n+1,1,n+1,0);↵
if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]);↵
if(u==1) ans=0;↵
}↵
else if(!ch[u][1]){↵
dfs(ch[u][0]);↵
rt[u]=rt[ch[u][0]];↵
if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]);↵
ll minn=tree[rt[u]].minn2;↵
mdf(rt[u],1,n+1,1,n+1,minn);↵
if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]);↵
if(u==1) ans=minn;↵
}↵
else{↵
ll x=ch[u][0],y=ch[u][1];↵
dfs(x);↵
dfs(y);↵
if(a[u]<=(n+1)){↵
upd(rt[x],1,n+1,a[u]);↵
upd(rt[y],1,n+1,a[u]);↵
}↵
ll minx=tree[rt[x]].minn2,miny=tree[rt[y]].minn2,k=min(query(rt[x],rt[y],1,n+1),minx+miny);↵
add(rt[x],1,n+1,1,n+1,miny);↵
add(rt[y],1,n+1,1,n+1,minx);↵
rt[u]=merge(rt[x],rt[y],1,n+1);↵
mdf(rt[u],1,n+1,1,n+1,k);↵
if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]);↵
if(u==1) ans=k;↵
}↵
}↵
il void clr(){↵
fr(i,1,n) ch[i][0]=ch[i][1]=rt[i]=0;↵
tot=0;↵
ans=inf;↵
}↵
int main(){↵
t=read();↵
while(t--){↵
n=read();↵
fr(i,1,n) a[i]=read();↵
fr(i,2,n){↵
ll x=read();↵
if(!ch[x][0]) ch[x][0]=i;↵
else ch[x][1]=i;↵
}↵
dfs(1);↵
writeln(ans);↵
clr();↵
}↵
}↵
/*↵
1↵
5↵
3 2 2 1 1↵
1 1 2 2↵
ans:↵
4 ↵
*/ ↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rating predictions (Inspired by sum's editorial)">↵
It seems like a joke now...↵
↵
| Person | A | B | C | D | E | F |↵
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |↵
| [user: zltzlt, 2024-5-31] | 800 | 1400 | 1600 | 2000 | 2300 | 2800 |↵
| [user: small_peter, 2024-5-31] | 800 | 1400 | 1700 | 1600 | | |↵
| [user: WRuperD, 2024-5-31] | 800 | 1300 | 1600 | 2000 | | 2800 |↵
| [user: yinhee, 2024-5-31] | 800 | 1000 | 1500 | 2100 | 2200 | 2700 |↵
| [user: sinsop90, 2024-5-31] | 1000 | 1300 | 1500 | 2000 | 2200 | |↵
| [user: Yujiahe,2024-05-28] | 800 | 1100 | 1600 | 1900 | | 2700 |↵
| [user: CharlieV, 2024-5-31] | | | | 2400 | 2500 | 3000 |↵
| [user: JWRuixi, 2024-5-31] | | | | 1800 | | |↵
| [user: Edwin__VanCleef, 2024-5-31] | | | 1600 | 1800 | |↵
| [user: QwQwf, 2024-5-31] | 1000 | 1600 | 2000 | 2100 | | |↵
| [user: wsc2008qwq, 2024-5-31] | 900 | 1000 | 1800 | 2500 | 2600 | |↵
| [user: starrykiller, 2024-5-31] | 900 | 1400 | 1700 | 1900 | | |↵
| [user: rui_er, 2024-5-31] | 800 | 1000 | 1600 | 2100 | 2500 | |↵
| [user: Jryno1, 2024-5-31] | 800 | 1200 | 1600 | 2100 | 2700 | |↵
| [user: StarSilk, 2024-5-31] | 800 | 1200 | 1600 | 2000 | 2500 | 3000 |↵
| [user: lovely-ckj, 2024-5-31] | 1000 | 1300 | 1800 | 2000 | | |↵
| [user: FengLing, 2024-5-31] | 800 | 1100 | 1400 | 2200 | | |↵
↵
| | A | B | C | D | E | F |↵
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |↵
| Average | 857 | 1236 | 1640 | 2029 | 2438 | 2833 |↵
| Actual | | | | | | |↵
</spoiler>↵
↵
[problem: 1981A]↵
↵
Idea: [user: zltzlt, 2024-5-31]↵
↵
<spoiler summary="Hint 1">↵
What is Piggy's optimal strategy?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What does $2l \le r$ mean?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1981A]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
int T;↵
scanf("%d", &T);↵
while (T--) {↵
int l, r;↵
scanf("%d%d", &l, &r);↵
printf("%d\n", __lg(r));↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem: 1981B]↵
↵
Idea: [user: zltzlt, 2024-5-31]↵
↵
<spoiler summary="Hint 1">↵
Consider each bit separately.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Calculate the time when the $d$-th bit of $a_n$ becomes $1$.↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
[tutorial:1981B]↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
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]$.↵
↵
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$.↵
↵
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$.↵
↵
Time complexity: $O(\log (n + m))$ per test case.↵
</spoiler>↵
↵
<spoiler summary="Code for Solution 1">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define pb emplace_back↵
#define fst first↵
#define scd second↵
#define mkp make_pair↵
#define mems(a, x) memset((a), (x), sizeof(a))↵
↵
using namespace std;↵
typedef long long ll;↵
typedef double db;↵
typedef unsigned long long ull;↵
typedef long double ldb;↵
typedef pair<ll, ll> pii;↵
↵
void solve() {↵
ll n, m;↵
scanf("%lld%lld", &n, &m);↵
ll ans = 0;↵
for (int i = 0; i <= 30; ++i) {↵
ll x = n & ((1LL << (i + 1)) - 1);↵
ll t = (1LL << i) - x;↵
if (n >= (1LL << i)) {↵
t = min(t, x + 1);↵
}↵
if (x >= (1LL << i) || t <= m) {↵
ans |= (1LL << i);↵
}↵
}↵
printf("%lld\n", ans);↵
}↵
↵
int main() {↵
int T = 1;↵
scanf("%d", &T);↵
while (T--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Code for Solution 2">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define pb emplace_back↵
#define fst first↵
#define scd second↵
#define mkp make_pair↵
#define mems(a, x) memset((a), (x), sizeof(a))↵
↵
using namespace std;↵
typedef long long ll;↵
typedef double db;↵
typedef unsigned long long ull;↵
typedef long double ldb;↵
typedef pair<ll, ll> pii;↵
↵
void solve() {↵
ll n, m;↵
scanf("%lld%lld", &n, &m);↵
ll l = max(0LL, n - m), r = n + m, ans = 0;↵
for (int i = 31; ~i; --i) {↵
if ((l & (1LL << i)) || (r & (1LL << i)) || (l >> (i + 1)) != (r >> (i + 1))) {↵
ans |= (1LL << i);↵
}↵
}↵
printf("%lld\n", ans);↵
}↵
↵
int main() {↵
int T = 1;↵
scanf("%d", &T);↵
while (T--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem: 1981C]↵
↵
Idea: [user: zltzlt, 2024-5-31]↵
↵
<spoiler summary="Hint 1">↵
Figure out the case where $a'_1 \ne -1, a'_n \ne -1$ and $a'_2 = a'_3 = \cdots = a'_{n - 1} = -1$ first.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Imagine a full binary tree. Consider the sequence as a walk on the full binary tree.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1981C]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define pb emplace_back↵
#define fst first↵
#define scd second↵
#define mkp make_pair↵
#define mems(a, x) memset((a), (x), sizeof(a))↵
↵
using namespace std;↵
typedef long long ll;↵
typedef double db;↵
typedef unsigned long long ull;↵
typedef long double ldb;↵
typedef pair<ll, ll> pii;↵
↵
const int maxn = 200100;↵
↵
int n, a[maxn];↵
↵
inline vector<int> path(int x, int y) {↵
vector<int> L, R;↵
while (__lg(x) > __lg(y)) {↵
L.pb(x);↵
x >>= 1;↵
}↵
while (__lg(y) > __lg(x)) {↵
R.pb(y);↵
y >>= 1;↵
}↵
while (x != y) {↵
L.pb(x);↵
R.pb(y);↵
x >>= 1;↵
y >>= 1;↵
}↵
L.pb(x);↵
reverse(R.begin(), R.end());↵
for (int x : R) {↵
L.pb(x);↵
}↵
return L;↵
}↵
↵
void solve() {↵
scanf("%d", &n);↵
int l = -1, r = -1;↵
vector<int> vc;↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &a[i]);↵
if (a[i] != -1) {↵
if (l == -1) {↵
l = i;↵
}↵
r = i;↵
vc.pb(i);↵
}↵
}↵
if (l == -1) {↵
for (int i = 1; i <= n; ++i) {↵
printf("%d%c", (i & 1) + 1, " \n"[i == n]);↵
}↵
return;↵
}↵
for (int i = l - 1; i; --i) {↵
a[i] = (((l - i) & 1) ? a[l] * 2 : a[l]);↵
}↵
for (int i = r + 1; i <= n; ++i) {↵
a[i] = (((i - r) & 1) ? a[r] * 2 : a[r]);↵
}↵
for (int _ = 1; _ < (int)vc.size(); ++_) {↵
int l = vc[_ - 1], r = vc[_];↵
vector<int> p = path(a[l], a[r]);↵
if (((int)p.size() & 1) != ((r - l + 1) & 1) || r - l + 1 < (int)p.size()) {↵
puts("-1");↵
return;↵
}↵
for (int i = 0; i < (int)p.size(); ++i) {↵
a[l + i] = p[i];↵
}↵
for (int i = l + (int)p.size(), o = 1; i <= r; ++i, o ^= 1) {↵
a[i] = (o ? a[i - 1] * 2 : a[i - 1] / 2);↵
}↵
}↵
for (int i = 1; i <= n; ++i) {↵
printf("%d%c", a[i], " \n"[i == n]);↵
}↵
}↵
↵
int main() {↵
int T = 1;↵
scanf("%d", &T);↵
while (T--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem: 1981D]↵
↵
Idea: [user: sinsop90, 2024-5-31]↵
↵
<spoiler summary="Hint 1">↵
$a_i$ should take different primes.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Transform it into a graph problem.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1981D]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define pb emplace_back↵
#define fst first↵
#define scd second↵
#define mkp make_pair↵
#define mems(a, x) memset((a), (x), sizeof(a))↵
↵
using namespace std;↵
typedef long long ll;↵
typedef double db;↵
typedef unsigned long long ull;↵
typedef long double ldb;↵
typedef pair<int, int> pii;↵
↵
const int maxn = 4000100;↵
const int N = 1000000;↵
↵
int n, a[maxn], pr[maxn], tot, stk[maxn], top;↵
bool vis[maxn];↵
↵
inline void init() {↵
for (int i = 2; i <= N; ++i) {↵
if (!vis[i]) {↵
pr[++tot] = i;↵
}↵
for (int j = 1; j <= tot && i * pr[j] <= N; ++j) {↵
vis[i * pr[j]] = 1;↵
if (i % pr[j] == 0) {↵
break;↵
}↵
}↵
}↵
mems(vis, 0);↵
}↵
↵
inline bool check(int x) {↵
if (x & 1) {↵
return x + 1 + x * (x - 1) / 2 >= n;↵
} else {↵
return x * (x - 1) / 2 - x / 2 + 2 + x >= n;↵
}↵
}↵
↵
vector<pii> G[10000];↵
↵
void dfs(int u) {↵
while (G[u].size()) {↵
pii p = G[u].back();↵
G[u].pop_back();↵
if (vis[p.scd]) {↵
continue;↵
}↵
vis[p.scd] = 1;↵
dfs(p.fst);↵
}↵
stk[++top] = pr[u];↵
}↵
↵
void solve() {↵
scanf("%d", &n);↵
int l = 1, r = 10000, ans = -1;↵
while (l <= r) {↵
int mid = (l + r) >> 1;↵
if (check(mid)) {↵
ans = mid;↵
r = mid - 1;↵
} else {↵
l = mid + 1;↵
}↵
}↵
for (int i = 1; i <= ans; ++i) {↵
vector<pii>().swap(G[i]);↵
}↵
int tot = 0;↵
for (int i = 1; i <= ans; ++i) {↵
for (int j = i; j <= ans; ++j) {↵
if (ans % 2 == 0 && i % 2 == 0 && i + 1 == j) {↵
continue;↵
}↵
G[i].pb(j, ++tot);↵
G[j].pb(i, tot);↵
}↵
}↵
for (int i = 1; i <= tot; ++i) {↵
vis[i] = 0;↵
}↵
top = 0;↵
dfs(1);↵
reverse(stk + 1, stk + top + 1);↵
for (int i = 1; i <= n; ++i) {↵
printf("%d%c", stk[i], " \n"[i == n]);↵
}↵
}↵
↵
int main() {↵
init();↵
int T = 1;↵
scanf("%d", &T);↵
while (T--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem: 1981E]↵
↵
Idea: [user: zltzlt, 2024-5-31]↵
<br>↵
Developed by [user: 244mhq, 2024-5-31].↵
↵
<spoiler summary="Hint 1">↵
Stop thinking about Boruvka.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Most of the edges in the graph are useless.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:1981E]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define pb emplace_back↵
#define fst first↵
#define scd second↵
#define mkp make_pair↵
#define mems(a, x) memset((a), (x), sizeof(a))↵
↵
using namespace std;↵
typedef long long ll;↵
typedef double db;↵
typedef unsigned long long ull;↵
typedef long double ldb;↵
typedef pair<int, int> pii;↵
↵
const int maxn = 1000100;↵
↵
int n, lsh[maxn], tot, fa[maxn];↵
pii b[maxn];↵
↵
struct node {↵
int l, r, x;↵
} a[maxn];↵
↵
struct edg {↵
int u, v, d;↵
edg(int a = 0, int b = 0, int c = 0) : u(a), v(b), d(c) {}↵
} E[maxn];↵
↵
int find(int x) {↵
return fa[x] == x ? x : fa[x] = find(fa[x]);↵
}↵
↵
inline bool merge(int x, int y) {↵
x = find(x);↵
y = find(y);↵
if (x != y) {↵
fa[x] = y;↵
return 1;↵
} else {↵
return 0;↵
}↵
}↵
↵
void solve() {↵
tot = 0;↵
cin >> n;↵
for (int i = 1; i <= n; ++i) {↵
cin >> a[i].l >> a[i].r >> a[i].x;↵
lsh[++tot] = a[i].l;↵
lsh[++tot] = (++a[i].r);↵
}↵
int m = 0;↵
sort(lsh + 1, lsh + tot + 1);↵
tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;↵
for (int i = 1; i <= n; ++i) {↵
a[i].l = lower_bound(lsh + 1, lsh + tot + 1, a[i].l) - lsh;↵
a[i].r = lower_bound(lsh + 1, lsh + tot + 1, a[i].r) - lsh;↵
b[++m] = mkp(a[i].l, i);↵
b[++m] = mkp(a[i].r, -i);↵
}↵
set<pii> S;↵
sort(b + 1, b + m + 1);↵
int tt = 0;↵
for (int i = 1; i <= m; ++i) {↵
int j = b[i].scd;↵
if (j > 0) {↵
auto it = S.insert(mkp(a[j].x, j)).fst;↵
if (it != S.begin()) {↵
int k = prev(it)->scd;↵
E[++tt] = edg(j, k, abs(a[j].x - a[k].x));↵
}↵
if (next(it) != S.end()) {↵
int k = next(it)->scd;↵
E[++tt] = edg(j, k, abs(a[j].x - a[k].x));↵
}↵
} else {↵
j = -j;↵
S.erase(mkp(a[j].x, j));↵
}↵
}↵
for (int i = 1; i <= n; ++i) {↵
fa[i] = i;↵
}↵
sort(E + 1, E + tt + 1, [&](const edg &a, const edg &b) {↵
return a.d < b.d;↵
});↵
ll ans = 0, cnt = 0;↵
for (int i = 1; i <= tt; ++i) {↵
if (merge(E[i].u, E[i].v)) {↵
++cnt;↵
ans += E[i].d;↵
}↵
}↵
cout << (cnt == n - 1 ? ans : -1) << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int T = 1;↵
cin >> T;↵
while (T--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem: 1981F]↵
↵
Idea: [user: yinhee, 2024-5-31]↵
<br>↵
Developed by [user: 244mhq, 2024-5-31] and [user: zltzlt, 2024-5-31].↵
<br>↵
Thanks [user: AFewSuns, 2024-5-31] and [user: crazy_sea, 2024-5-31] for discovering Solution 2, which runs faster than Solution 1!↵
↵
<spoiler summary="Hint 1">↵
Try some dp that takes $O(n^2)$ time.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What's the maximum MEX in the optimal good set of paths?↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
[tutorial:1981F]↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
Read the $O(n^2)$ part of Solution 1 first.↵
↵
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.↵
↵
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.↵
↵
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$.↵
↵
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}$.↵
↵
Time complexity: $\mathcal{O}(n \log n)$ per test case.↵
</spoiler>↵
↵
<spoiler summary="Code for Solution 1">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define pb emplace_back↵
#define fst first↵
#define scd second↵
#define mkp make_pair↵
#define mems(a, x) memset((a), (x), sizeof(a))↵
↵
using namespace std;↵
typedef long long ll;↵
typedef double db;↵
typedef unsigned long long ull;↵
typedef long double ldb;↵
typedef pair<ll, ll> pii;↵
↵
const int maxn = 25050;↵
const int inf = 0x3f3f3f3f;↵
↵
int n, m, a[maxn], f[maxn][4000];↵
vector<int> G[maxn];↵
↵
void dfs(int u) {↵
if (G[u].empty()) {↵
for (int i = 1; i <= m; ++i) {↵
f[u][i] = (i == a[u] ? inf : 0);↵
}↵
return;↵
}↵
if ((int)G[u].size() == 1) {↵
int x = G[u][0];↵
dfs(x);↵
int mn = inf;↵
for (int i = 1; i <= m; ++i) {↵
if (i != a[u]) {↵
mn = min(mn, f[x][i] + i);↵
}↵
}↵
if (u == 1) {↵
printf("%d\n", mn);↵
return;↵
}↵
for (int i = 1; i <= m; ++i) {↵
f[u][i] = (i == a[u] ? inf : min(f[x][i], mn));↵
}↵
return;↵
}↵
int x = G[u][0], y = G[u][1], mnx = inf, mny = inf, k = inf;↵
dfs(x);↵
dfs(y);↵
for (int i = 1; i <= m; ++i) {↵
if (i != a[u]) {↵
mnx = min(mnx, f[x][i] + i);↵
mny = min(mny, f[y][i] + i);↵
k = min(k, f[x][i] + f[y][i] + i);↵
}↵
}↵
k = min(k, mnx + mny);↵
if (u == 1) {↵
printf("%d\n", k);↵
return;↵
}↵
for (int i = 1; i <= m; ++i) {↵
f[u][i] = (i == a[u] ? inf : min({f[x][i] + mny, f[y][i] + mnx, k}));↵
}↵
}↵
↵
void solve() {↵
scanf("%d", &n);↵
m = min(n + 1, 3863);↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &a[i]);↵
vector<int>().swap(G[i]);↵
}↵
for (int i = 2, p; i <= n; ++i) {↵
scanf("%d", &p);↵
G[p].pb(i);↵
}↵
dfs(1);↵
}↵
↵
int main() {↵
int T = 1;↵
scanf("%d", &T);↵
while (T--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Code for Solution 2">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
namespace my_std{↵
#define ll long long↵
#define bl bool↵
ll my_pow(ll a,ll b,ll mod){↵
ll res=1;↵
if(!b) return 1;↵
while(b){↵
if(b&1) res=(res*a)%mod;↵
a=(a*a)%mod;↵
b>>=1;↵
}↵
return res;↵
}↵
ll qpow(ll a,ll b){↵
ll res=1;↵
if(!b) return 1;↵
while(b){↵
if(b&1) res*=a;↵
a*=a;↵
b>>=1;↵
}↵
return res;↵
}↵
#define db double↵
#define pf printf↵
#define pc putchar↵
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)↵
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)↵
#define go(u) for(ll i=head[u];i;i=e[i].nxt)↵
#define enter pc('\n')↵
#define space pc(' ')↵
#define fir first↵
#define sec second↵
#define MP make_pair↵
#define il inline↵
#define inf 1e18↵
#define random(x) rand()*rand()%(x)↵
#define inv(a,mod) my_pow((a),(mod-2),(mod))↵
il ll read(){↵
ll sum=0,f=1;↵
char ch=0;↵
while(!isdigit(ch)){↵
if(ch=='-') f=-1;↵
ch=getchar();↵
}↵
while(isdigit(ch)){↵
sum=sum*10+(ch^48);↵
ch=getchar();↵
}↵
return sum*f;↵
}↵
il void write(ll x){↵
if(x<0){↵
x=-x;↵
pc('-');↵
}↵
if(x>9) write(x/10);↵
pc(x%10+'0');↵
}↵
il void writeln(ll x){↵
write(x);↵
enter;↵
}↵
il void writesp(ll x){↵
write(x);↵
space;↵
}↵
}↵
using namespace my_std;↵
#define LC tree[x].lc↵
#define RC tree[x].rc↵
ll t,n,a[25025],ch[25025][2],ans=inf;↵
ll rt[25025],tot=0;↵
struct node{↵
ll minn1,minn2,lz,lzmin,lc,rc;↵
il void addtag(ll v,ll vmin,ll l){↵
minn1=min(minn1+v,vmin);↵
minn2=min(minn2+v,vmin+l);↵
lz+=v;↵
lzmin=min(lzmin+v,vmin);↵
}↵
}tree[1000010];↵
il void pushup(ll x){↵
tree[x].minn1=min(tree[LC].minn1,tree[RC].minn1);↵
tree[x].minn2=min(tree[LC].minn2,tree[RC].minn2);↵
}↵
il ll newnode(){↵
tree[++tot]=(node){(ll)inf,(ll)inf,0,(ll)inf,0,0};↵
return tot;↵
}↵
il void pushdown(ll x,ll l,ll r){↵
if(!LC) LC=newnode();↵
if(!RC) RC=newnode();↵
ll mid=(l+r)>>1;↵
tree[LC].addtag(tree[x].lz,tree[x].lzmin,l);↵
tree[RC].addtag(tree[x].lz,tree[x].lzmin,mid+1);↵
tree[x].lz=0;↵
tree[x].lzmin=inf;↵
}↵
void upd(ll &x,ll l,ll r,ll pos){↵
if(!x) x=newnode();↵
if(l==r){↵
tree[x].minn1=tree[x].minn2=inf;↵
return;↵
}↵
ll mid=(l+r)>>1;↵
pushdown(x,l,r);↵
if(pos<=mid) upd(LC,l,mid,pos);↵
else upd(RC,mid+1,r,pos);↵
pushup(x);↵
}↵
void add(ll &x,ll l,ll r,ll ql,ll qr,ll v){↵
if(!x) x=newnode();↵
if(ql<=l&&r<=qr){↵
tree[x].addtag(v,(ll)inf,l);↵
return;↵
}↵
ll mid=(l+r)>>1;↵
pushdown(x,l,r);↵
if(ql<=mid) add(LC,l,mid,ql,qr,v);↵
if(mid<qr) add(RC,mid+1,r,ql,qr,v);↵
pushup(x);↵
}↵
void mdf(ll &x,ll l,ll r,ll ql,ll qr,ll v){↵
if(!x) x=newnode();↵
if(ql<=l&&r<=qr){↵
tree[x].addtag(0,v,l);↵
return;↵
}↵
ll mid=(l+r)>>1;↵
pushdown(x,l,r);↵
if(ql<=mid) mdf(LC,l,mid,ql,qr,v);↵
if(mid<qr) mdf(RC,mid+1,r,ql,qr,v);↵
pushup(x);↵
}↵
ll merge(ll x,ll y,ll l,ll r){↵
if(!LC&&!RC){↵
tree[y].addtag(0,tree[x].minn1,l);↵
return y;↵
}↵
if(!tree[y].lc&&!tree[y].rc){↵
tree[x].addtag(0,tree[y].minn1,l);↵
return x;↵
}↵
ll mid=(l+r)>>1;↵
pushdown(x,l,r);↵
pushdown(y,l,r);↵
LC=merge(LC,tree[y].lc,l,mid);↵
RC=merge(RC,tree[y].rc,mid+1,r);↵
pushup(x);↵
return x;↵
}↵
ll query(ll x,ll y,ll l,ll r){↵
if(!LC&&!RC) return tree[x].minn1+tree[y].minn2;↵
if(!tree[y].lc&&!tree[y].rc) return tree[y].minn1+tree[x].minn2;↵
ll mid=(l+r)>>1,res=inf;↵
pushdown(x,l,r);↵
pushdown(y,l,r);↵
res=min(res,query(LC,tree[y].lc,l,mid));↵
res=min(res,query(RC,tree[y].rc,mid+1,r));↵
return res;↵
}↵
void dfs(ll u){↵
if(!ch[u][0]){↵
mdf(rt[u],1,n+1,1,n+1,0);↵
if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]);↵
if(u==1) ans=0;↵
}↵
else if(!ch[u][1]){↵
dfs(ch[u][0]);↵
rt[u]=rt[ch[u][0]];↵
if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]);↵
ll minn=tree[rt[u]].minn2;↵
mdf(rt[u],1,n+1,1,n+1,minn);↵
if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]);↵
if(u==1) ans=minn;↵
}↵
else{↵
ll x=ch[u][0],y=ch[u][1];↵
dfs(x);↵
dfs(y);↵
if(a[u]<=(n+1)){↵
upd(rt[x],1,n+1,a[u]);↵
upd(rt[y],1,n+1,a[u]);↵
}↵
ll minx=tree[rt[x]].minn2,miny=tree[rt[y]].minn2,k=min(query(rt[x],rt[y],1,n+1),minx+miny);↵
add(rt[x],1,n+1,1,n+1,miny);↵
add(rt[y],1,n+1,1,n+1,minx);↵
rt[u]=merge(rt[x],rt[y],1,n+1);↵
mdf(rt[u],1,n+1,1,n+1,k);↵
if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u]);↵
if(u==1) ans=k;↵
}↵
}↵
il void clr(){↵
fr(i,1,n) ch[i][0]=ch[i][1]=rt[i]=0;↵
tot=0;↵
ans=inf;↵
}↵
int main(){↵
t=read();↵
while(t--){↵
n=read();↵
fr(i,1,n) a[i]=read();↵
fr(i,2,n){↵
ll x=read();↵
if(!ch[x][0]) ch[x][0]=i;↵
else ch[x][1]=i;↵
}↵
dfs(1);↵
writeln(ans);↵
clr();↵
}↵
}↵
/*↵
1↵
5↵
3 2 2 1 1↵
1 1 2 2↵
ans:↵
4 ↵
*/ ↵
~~~~~↵
↵
</spoiler>↵
↵
