By observing the example, we can see that there is no solution when $$$n$$$ is even.

#include <bits/stdc++.h>
using namespace std;

int main() {
	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		if (n & 1) {
			cout << n << ' ';
			for (int i = 1; i < n; ++i) {
				cout << i << " \n"[i == n - 1];
			}
		} else {
			cout << "-1\n";
		}
	}
	return 0;
}

Consider the position of the minimum value after rearranging the sequence.

What kind of numbers should be placed on the $$$\min$$$ side, and what kind should be placed on the $$$\gcd$$$ side?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		vector<ll> a(n);
		for (ll &x : a) {
			cin >> x;
		}
		int p = min_element(a.begin(), a.end()) - a.begin();
		ll g = 0;
		for (int i = 0; i < n; ++i) {
			if (i != p && a[i] % a[p] == 0) {
				g = __gcd(g, a[i]);
			}
		}
		cout << (g == a[p] ? "Yes\n" : "No\n");
	}
	return 0;
}

Will the $$$b_i$$$ corresponding to a given $$$a_i$$$ change?

Individually place each pair corresponding to $$$(a_i, b_i)$$$ (i.e., $$$(b_i, a_i)$$$) at position $$$n - i + 1$$$.

#include <bits/stdc++.h>
using namespace std;

const int maxn = 200100;

int n, a[maxn], b[maxn], m, p[maxn], ans[maxn][2];

inline void work(int x, int y) {
	if (x == y) {
		return;
	}
	ans[++m][0] = x;
	ans[m][1] = y;
	swap(a[x], a[y]);
	swap(p[a[x]], p[a[y]]);
	swap(b[x], b[y]);
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[a[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		cin >> b[i];
	}
	m = 0;
	int x = 0;
	for (int i = 1; i <= n; ++i) {
		if (a[i] == b[i]) {
			if (n % 2 == 0 || x) {
				cout << "-1\n";
				return;
			}
			x = i;
		} else if (b[p[b[i]]] != a[i]) {
			cout << "-1\n";
			return;
		}
	}
	if (n & 1) {
		work(x, (n + 1) / 2);
	}
	for (int i = 1; i <= n / 2; ++i) {
		work(p[b[i]], n - i + 1);
	}
	cout << m << '\n';
	for (int i = 1; i <= m; ++i) {
		cout << ans[i][0] << ' ' << ans[i][1] << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

Treat "at most $$$m$$$ operations" as "exactly $$$m$$$ operations".

What is the maximum value of $$$f(a)$$$?

Ensure that the distance between each pair of identical numbers is at least $$$k$$$.

#include <bits/stdc++.h>
using namespace std;

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n, m, k;
		cin >> n >> m >> k;
		for (int i = 0; i < n; ++i) {
			cout << i % (n < (m + 1) * k ? k : n / (m + 1)) << " \n"[i == n - 1];
		}
	}
	return 0;
}

Transform the calculation method of $$$\operatorname{mex}$$$.

Try to come up with an $$$O(n^3)$$$ approach and then optimize it to $$$O(n^2)$$$.

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5050;
const int mod = 1000000007;

int n, a[maxn], fac[maxn], C[maxn][maxn], b[maxn], d[maxn][maxn];
bool vis[maxn];

void solve() {
	cin >> n;
	for (int i = 0; i <= n; ++i) {
		vis[i] = 0;
		for (int j = 0; j <= n; ++j) {
			d[i][j] = 0;
		}
	}
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		fac[i] = 1LL * fac[i - 1] * i % mod;
		b[i] = b[i - 1] + (a[i] == -1);
		if (a[i] != -1) {
			vis[a[i]] = 1;
		}
	}
	for (int i = 0; i <= n; ++i) {
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; ++j) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
		}
	}
	int mn1 = n;
	for (int i = 1; i <= n; ++i) {
		int mn2 = n;
		for (int j = n; j >= i; --j) {
			int x = b[j] - b[i - 1], y = min(mn1, mn2);
			++d[x][0];
			--d[x][y];
			if (a[j] != -1) {
				mn2 = min(mn2, a[j]);
			}
		}
		if (a[i] != -1) {
			mn1 = min(mn1, a[i]);
		}
	}
	for (int i = 0; i <= b[n]; ++i) {
		for (int j = 1; j <= n; ++j) {
			d[i][j] += d[i][j - 1];
		}
	}
	int ans = 0, cnt = 0;
	for (int i = 0; i < n; ++i) {
		cnt += (!vis[i]);
		for (int j = cnt; j <= b[n]; ++j) {
			ans = (ans + 1LL * C[j][cnt] * fac[cnt] % mod * fac[b[n] - cnt] % mod * d[j][i]) % mod;
		}
	}
	cout << ans << '\n';
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

What kind of permutation $$$b$$$ is good?

Consider transforming this problem into a classic greedy algorithm problem.

#include <bits/stdc++.h>
using namespace std;

const int maxn = 500100;

int n, a[maxn], b[maxn], c[maxn], p[maxn], q[maxn];

struct node {
	int r, x;
	node(int a = 0, int b = 0) : r(a), x(b) {}
};

inline bool operator < (const node &a, const node &b) {
	return a.r > b.r || (a.r == b.r && a.x > b.x);
}

vector<node> vc[maxn];

struct DS1 {
	int c[maxn];
	
	inline void init() {
		for (int i = 0; i <= n; ++i) {
			c[i] = 0;
		}
	}
	
	inline void update(int x, int d) {
		for (int i = x; i <= n; i += (i & (-i))) {
			c[i] = max(c[i], d);
		}
	}
	
	inline int query(int x) {
		int res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res = max(res, c[i]);
		}
		return res;
	}
} T1;

struct DS2 {
	int c[maxn];
	
	inline void init() {
		for (int i = 0; i <= n; ++i) {
			c[i] = n + 1;
		}
	}
	
	inline void update(int x, int d) {
		for (int i = x; i; i -= (i & (-i))) {
			c[i] = min(c[i], d);
		}
	}
	
	inline int query(int x) {
		int res = n + 1;
		for (int i = x; i <= n; i += (i & (-i))) {
			res = min(res, c[i]);
		}
		return res;
	}
} T2;

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[a[i]] = i;
		q[i] = 0;
		vector<node>().swap(vc[i]);
	}
	for (int i = 1; i <= n; ++i) {
		cin >> b[i];
		if (b[i]) {
			q[b[i]] = i;
		}
	}
	T1.init();
	for (int i = 1; i <= n; ++i) {
		if (q[i]) {
			if (T1.query(p[i]) > q[i]) {
				cout << "-1\n";
				return;
			}
			T1.update(p[i], q[i]);
		}
	}
	T1.init();
	T2.init();
	for (int i = 1; i <= n; ++i) {
		if (q[a[i]]) {
			T1.update(a[i], q[a[i]]);
		} else {
			c[i] = T1.query(a[i]) + 1;
		}
	}
	for (int i = n; i; --i) {
		if (q[a[i]]) {
			T2.update(a[i], q[a[i]]);
		} else {
			int r = T2.query(a[i]) - 1;
			if (c[i] > r) {
				cout << "-1\n";
				return;
			}
			vc[c[i]].emplace_back(r, a[i]);
		}
	}
	priority_queue<node> pq;
	for (int i = 1; i <= n; ++i) {
		for (node u : vc[i]) {
			pq.push(u);
		}
		if (!b[i]) {
			if (pq.empty() || pq.top().r < i) {
				cout << "-1\n";
				return;
			}
			b[i] = pq.top().x;
			pq.pop();
		}
	}
	for (int i = 1; i <= n; ++i) {
		cout << b[i] << " \n"[i == n];
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

What is the value of $$$f(c)$$$?

Try DP.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n + 1, -1);
	vector< vector<ll> > f(n + 1, vector<ll>(n + 1, 1e18));
	for (int i = 1, x; i <= n; ++i) {
		cin >> x;
		if (x) {
			a[x] = i & 1;
		}
	}
	if (a[1] != 1) {
		f[1][0] = 0;
	}
	if (a[1] != 0) {
		f[1][1] = 0;
	}
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j <= i; ++j) {
			f[i][j] += j * (n / 2 - (i - j)) + (i - j) * ((n + 1) / 2 - j);
			if (a[i + 1] != 1) {
				f[i + 1][j] = min(f[i + 1][j], f[i][j]);
			}
			if (a[i + 1] != 0) {
				f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j]);
			}
		}
	}
	ll ans = -f[n][(n + 1) / 2];
	for (int i = 1; i <= n; ++i) {
		ans += i * i;
	}
	cout << ans << '\n';
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

Optimize the DP in G1.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 500100;

int n, a[maxn];
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int p[maxn], nt, ls[maxn], rs[maxn], sz[maxn];
bool vis[maxn];

struct vec {
	ll a0, a1, a2;
	vec(ll a = 0, ll b = 0, ll c = 0) : a0(a), a1(b), a2(c) {}
} val[maxn];

struct mat {
	ll a00, a01, a02, a10, a11, a12, a20, a21, a22;
	mat(ll a = 0, ll b = 0, ll c = 0, ll d = 0, ll e = 0, ll f = 0, ll g = 0, ll h = 0, ll i = 0) : a00(a), a01(b), a02(c), a10(d), a11(e), a12(f), a20(g), a21(h), a22(i) {}
} I, tag[maxn];

inline vec operator * (const vec &a, const mat &b) {
	vec res;
	res.a0 = a.a0 * b.a00 + a.a1 * b.a10 + a.a2 * b.a20;
	res.a1 = a.a0 * b.a01 + a.a1 * b.a11 + a.a2 * b.a21;
	res.a2 = a.a0 * b.a02 + a.a1 * b.a12 + a.a2 * b.a22;
	return res;
}

inline mat operator * (const mat &a, const mat &b) {
	mat res;
	res.a00 = a.a00 * b.a00 + a.a01 * b.a10 + a.a02 * b.a20;
	res.a01 = a.a00 * b.a01 + a.a01 * b.a11 + a.a02 * b.a21;
	res.a02 = a.a00 * b.a02 + a.a01 * b.a12 + a.a02 * b.a22;
	res.a10 = a.a10 * b.a00 + a.a11 * b.a10 + a.a12 * b.a20;
	res.a11 = a.a10 * b.a01 + a.a11 * b.a11 + a.a12 * b.a21;
	res.a12 = a.a10 * b.a02 + a.a11 * b.a12 + a.a12 * b.a22;
	res.a20 = a.a20 * b.a00 + a.a21 * b.a10 + a.a22 * b.a20;
	res.a21 = a.a20 * b.a01 + a.a21 * b.a11 + a.a22 * b.a21;
	res.a22 = a.a20 * b.a02 + a.a21 * b.a12 + a.a22 * b.a22;
	return res;
}

inline void init() {
	for (int i = 0; i <= nt; ++i) {
		p[i] = ls[i] = rs[i] = sz[i] = 0;
		val[i] = vec();
		tag[i] = I;
		vis[i] = 0;
	}
	nt = 0;
}

inline int newnode(ll x, ll y) {
	int u = ++nt;
	p[u] = rnd();
	ls[u] = rs[u] = 0;
	sz[u] = 1;
	val[u] = vec(x, y, 1);
	tag[u] = I;
	vis[u] = 0;
	return u;
}

inline void pushup(int x) {
	sz[x] = sz[ls[x]] + sz[rs[x]] + 1;
}

inline void pushtag(int x, const mat &y) {
	if (!x) {
		return;
	}
	val[x] = val[x] * y;
	tag[x] = tag[x] * y;
	vis[x] = 1;
}

inline void pushdown(int x) {
	if (!vis[x]) {
		return;
	}
	pushtag(ls[x], tag[x]);
	pushtag(rs[x], tag[x]);
	vis[x] = 0;
	tag[x] = I;
}

void split(int u, int &x, int &y) {
	if (!u) {
		x = y = 0;
		return;
	}
	pushdown(u);
	if (val[u].a0 < 0) {
		x = u;
		split(rs[u], rs[u], y);
	} else {
		y = u;
		split(ls[u], x, ls[u]);
	}
	pushup(u);
}

int merge(int x, int y) {
	if (!x || !y) {
		return x | y;
	}
	pushdown(x);
	pushdown(y);
	if (p[x] < p[y]) {
		rs[x] = merge(rs[x], y);
		pushup(x);
		return x;
	} else {
		ls[y] = merge(x, ls[y]);
		pushup(y);
		return y;
	}
}

ll f[maxn], tot;

void dfs(int u) {
	if (!u) {
		return;
	}
	pushdown(u);
	dfs(ls[u]);
	f[++tot] = val[u].a0;
	dfs(rs[u]);
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		a[i] = -1;
	}
	for (int i = 1, x; i <= n; ++i) {
		cin >> x;
		if (x) {
			a[x] = (i & 1);
		}
	}
	init();
	int rt = 0;
	ll l = 0, r = 0, x = 0;
	if (a[1] == 1) {
		l = r = 1;
	} else if (a[1] == -1) {
		rt = newnode(0, 1);
		r = 1;
	}
	for (ll i = 1; i < n; ++i) {
		x += l * l * 2 + (-i - i - (n & 1)) * l + i * ((n + 1) / 2);
		pushtag(rt, mat(1, 0, 0, 4, 1, 0, -i - i - (n & 1) - 2, 0, 1));
		if (a[i + 1] == 1) {
			pushtag(rt, mat(1, 0, 0, 0, 1, 0, 0, 1, 1));
			++l;
			++r;
		} else if (a[i + 1] == -1) {
			int u, v;
			split(rt, u, v);
			pushtag(v, mat(1, 0, 0, 0, 1, 0, 0, 1, 1));
			rt = merge(merge(u, newnode(0, l + 1 + sz[u])), v);
			++r;
		}
	}
	tot = 0;
	dfs(rt);
	ll ans = -x;
	for (int i = 1; i <= (n + 1) / 2 - l; ++i) {
		ans -= f[i];
	}
	for (ll i = 1; i <= n; ++i) {
		ans += i * i;
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	I.a00 = I.a11 = I.a22 = 1;
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

Extract the longest contiguous segments in $$$s$$$ where the values remain the same.

According to greedy matching, an $$$O(n^2)$$$ DP can be obtained.

Optimize the DP from $$$O(n^2)$$$ to $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2000100;
const ll mod = 1000000007;

int n, a[maxn], m, nxt[maxn], stk[maxn], top;
ll f[maxn], d[maxn];
char s[maxn];

inline ll calc() {
	top = 0;
	for (int i = m; i >= 1; i -= 2) {
		while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) {
			--top;
		}
		nxt[i] = stk[top];
		stk[++top] = i;
	}
	top = 0;
	for (int i = m - 1; i >= 1; i -= 2) {
		while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) {
			--top;
		}
		nxt[i] = stk[top];
		stk[++top] = i;
	}
	for (int i = 1; i < m; ++i) {
		f[i] = d[i] = 0;
	}
	f[1] = a[1];
	for (int i = 3; i < m; i += 2) {
		f[i] = 1;
	}
	ll ans = 0;
	for (int i = 1; i < m; ++i) {
		if (i >= 3) {
			d[i] = (d[i] + d[i - 2]) % mod;
		}
		f[i] = (f[i] + d[i]) % mod;
		int j = i + 1, x = 0;
		while (j < m) {
			int k = (nxt[j] ? nxt[j] : m);
			f[j] = (f[j] + f[i] * (a[j] - x)) % mod;
			x = a[j] + (k - j) / 2 - 1;
			d[j + 2] = (d[j + 2] + f[i]) % mod;
			d[k] = (d[k] - f[i] + mod) % mod;
			j = k;
		}
		if ((m - i) & 1) {
			ans = (ans + f[i]) % mod;
		}
	}
	return ans * a[m] % mod;
}

void solve() {
	cin >> n >> s;
	m = 0;
	for (int i = 0, j = 0; i < n; i = (++j)) {
		while (j + 1 < n && s[j + 1] == s[i]) {
			++j;
		}
		a[++m] = j - i + 1;
	}
	if (m == 1) {
		cout << n - 1 << '\n';
		return;
	}
	if (m == 2) {
		cout << 1LL * a[1] * a[2] % mod << '\n';
		return;
	}
	ll ans = calc();
	--m;
	for (int i = 1; i <= m; ++i) {
		a[i] = a[i + 1];
	}
	a[1] = 1;
	ans = (ans + calc()) % mod;
	cout << ans << '\n';
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2000100;
const ll mod = 1000000007;

int n, a[maxn], m, nxt[maxn], stk[maxn], top;
ll f[maxn], g[maxn], d[maxn];
char s[maxn];

inline ll calc() {
	top = 0;
	for (int i = m; i >= 1; i -= 2) {
		while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) {
			--top;
		}
		nxt[i] = stk[top];
		stk[++top] = i;
	}
	top = 0;
	for (int i = m - 1; i >= 1; i -= 2) {
		while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) {
			--top;
		}
		nxt[i] = stk[top];
		stk[++top] = i;
	}
	for (int i = 1; i < m; ++i) {
		f[i] = g[i] = d[i] = 0;
	}
	f[1] = a[1];
	for (int i = 3; i < m; i += 2) {
		f[i] = 1;
	}
	ll ans = 0;
	for (int i = 1; i < m; ++i) {
		if (i >= 3) {
			d[i] = (d[i] + d[i - 2]) % mod;
		}
		f[i] = (f[i] + d[i]) % mod;
		g[i + 1] = (g[i + 1] + f[i]) % mod;
		f[i + 1] = (f[i + 1] + f[i] * a[i + 1]) % mod;
		d[i + 2] = (d[i + 2] + g[i]) % mod;
		if (nxt[i]) {
			g[nxt[i]] = (g[nxt[i]] + g[i]) % mod;
			f[nxt[i]] = (f[nxt[i]] + g[i] * (a[nxt[i]] - a[i] - (nxt[i] - i) / 2 + 1)) % mod;
			d[nxt[i]] = (d[nxt[i]] - g[i] + mod) % mod;
		}
		if ((m - i) & 1) {
			ans = (ans + f[i]) % mod;
		}
	}
	return ans * a[m] % mod;
}

void solve() {
	cin >> n >> s;
	m = 0;
	for (int i = 0, j = 0; i < n; i = (++j)) {
		while (j + 1 < n && s[j + 1] == s[i]) {
			++j;
		}
		a[++m] = j - i + 1;
	}
	if (m == 1) {
		cout << n - 1 << '\n';
		return;
	}
	if (m == 2) {
		cout << 1LL * a[1] * a[2] % mod << '\n';
		return;
	}
	ll ans = calc();
	--m;
	for (int i = 1; i <= m; ++i) {
		a[i] = a[i + 1];
	}
	a[1] = 1;
	ans = (ans + calc()) % mod;
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

The first character of $$$t_1$$$ isn't equal to the last character of $$$t_k$$$.

#include <cstdio>

const int maxn = 110;

int n;
char s[maxn];

void solve() {
	scanf("%d%s", &n, s + 1);
	puts(s[1] != s[n] ? "Yes" : "No");
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Try to rephrase the operations of both players.

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100100;

int n, a[maxn];

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	sort(a + 1, a + n + 1, greater<int>());
	printf("%d\n", a[(n + 1) / 2]);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

You should understand what is a good pair.

#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;
pii a[99];
char s[maxn];

void solve() {
	scanf("%d%s", &n, s + 1);
	for (int i = 0; i < 26; ++i) {
		a[i] = mkp(0, i);
	}
	for (int i = 1; i <= n; ++i) {
		++a[s[i] - 'a'].fst;
	}
	sort(a, a + 26, greater<pii>());
	queue<pii> q;
	while (a[0].fst > a[1].fst) {
		putchar('a' + a[0].scd);
		--a[0].fst;
	}
	for (int i = 0; i < 26; ++i) {
		q.push(a[i]);
	}
	while (q.size()) {
		pii p = q.front();
		q.pop();
		if (!p.fst) {
			continue;
		}
		putchar('a' + p.scd);
		--p.fst;
		q.push(p);
	}
	putchar('\n');
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Choose the same integer twice.

#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;

ll n, m, a[maxn];
bool vis[maxn];

void solve() {
	scanf("%lld%lld", &n, &m);
	ll k = 0;
	while (n--) {
		int t;
		scanf("%d", &t);
		for (int i = 0; i <= t + 5; ++i) {
			vis[i] = 0;
		}
		for (int i = 1; i <= t; ++i) {
			scanf("%lld", &a[i]);
			if (a[i] <= t + 4) {
				vis[a[i]] = 1;
			}
		}
		ll mex = 0;
		while (vis[mex]) {
			++mex;
		}
		vis[mex] = 1;
		while (vis[mex]) {
			++mex;
		}
		k = max(k, mex);
	}
	printf("%lld\n", k >= m ? (m + 1) * k : k * k + (m + k) * (m - k + 1) / 2);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Construct a directed graph and rephrase the operation.

#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;

ll n, m, a[maxn], f[maxn];
pii b[maxn];
bool vis[maxn];
vector<int> G[maxn];

inline ll calc(ll l, ll r) {
	return (l + r) * (r - l + 1) / 2;
}

void solve() {
	scanf("%lld%lld", &n, &m);
	ll t = -1, ans = 0, k = 0;
	for (int i = 1, l; i <= n; ++i) {
		scanf("%d", &l);
		for (int j = 1; j <= l; ++j) {
			scanf("%lld", &a[j]);
			if (a[j] < maxn) {
				vis[a[j]] = 1;
			}
		}
		ll u = 0;
		while (vis[u]) {
			++u;
		}
		t = max(t, u);
		ll v = u;
		vis[u] = 1;
		while (vis[v]) {
			++v;
		}
		b[i] = mkp(u, v);
		k = max(k, v);
		vis[u] = 0;
		for (int j = 1; j <= l; ++j) {
			if (a[j] < maxn) {
				vis[a[j]] = 0;
			}
		}
	}
	for (int i = 0; i <= k; ++i) {
		vector<int>().swap(G[i]);
	}
	for (int i = 1; i <= n; ++i) {
		G[b[i].fst].pb(b[i].scd);
	}
	for (int u = k; ~u; --u) {
		f[u] = u;
		for (int v : G[u]) {
			f[u] = max(f[u], f[v]);
		}
		if ((int)G[u].size() >= 2) {
			t = max(t, f[u]);
		}
	}
	for (int i = 0; i <= min(k, m); ++i) {
		ans += max(t, f[i]);
	}
	if (k < m) {
		ans += calc(k + 1, m);
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Divide all numbers into small numbers and large numbers.

Use DP.

#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 = 5050;

int n, m, f[maxn][maxn], a[maxn], b[maxn];

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n + 1; ++i) {
		for (int j = 0; j <= n + 1; ++j) {
			f[i][j] = -1e9;
		}
		a[i] = 0;
	}
	for (int i = 1, l, r; i <= m; ++i) {
		scanf("%d%d", &l, &r);
		a[l] = r;
	}
	f[0][0] = 0;
	for (int i = 1; i <= n; ++i) {
		if (a[i]) {
			int p = a[i];
			for (int j = 0; j < i; ++j) {
				for (int k = 1; k <= p - i; ++k) {
					f[p][j + k] = max(f[p][j + k], f[i - 1][j] + (p - i + 1 - k) * j);
				}
			}
			i = p;
		} else {
			for (int j = 0; j <= i; ++j) {
				f[i][j] = f[i - 1][j] + j;
				if (j) {
					f[i][j] = max(f[i][j], f[i - 1][j - 1]);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; ++i) {
		ans = max(ans, f[n][i] + i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
	}
	printf("%d\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Try to handle overlapping intervals.

#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 = 5050;
const int inf = 0x3f3f3f3f;

int n, m, b[maxn], c[maxn], f[maxn][maxn];
struct node {
	int l, r;
} a[maxn];

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		c[i] = -1;
		b[i] = 0;
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &a[i].l, &a[i].r);
	}
	if (!m) {
		printf("%d\n", n * (n - 1) / 2);
		return;
	}
	sort(a + 1, a + m + 1, [&](const node &a, const node &b) {
		return a.l < b.l;
	});
	int mnl = a[1].l, mxl = a[1].l, mnr = a[1].r, mxr = a[1].r;
	for (int i = 2; i <= m + 1; ++i) {
		if (i == m + 1 || a[i].l > mxr) {
			if (mxl >= mnr) {
				puts("-1");
				return;
			}
			for (int j = mnl; j < mxl; ++j) {
				c[j] = 0;
			}
			for (int j = mnr + 1; j <= mxr; ++j) {
				c[j] = 1;
			}
			b[mxl] = mnr;
			mnl = mxl = a[i].l;
			mnr = mxr = a[i].r;
		} else {
			mnl = min(mnl, a[i].l);
			mxl = max(mxl, a[i].l);
			mnr = min(mnr, a[i].r);
			mxr = max(mxr, a[i].r);
		}
	}
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) {
			f[i][j] = -inf;
		}
	}
	f[0][0] = 0;
	for (int i = 1; i <= n; ++i) {
		if (b[i]) {
			int p = b[i];
			for (int j = 0; j < i; ++j) {
				for (int k = 1; k <= p - i; ++k) {
					f[p][j + k] = max(f[p][j + k], f[i - 1][j] + (p - i + 1 - k) * j);
				}
			}
			i = p;
		} else if (c[i] == 1) {
			for (int j = 1; j <= i; ++j) {
				f[i][j] = f[i - 1][j - 1];
			}
		} else if (c[i] == 0) {
			for (int j = 0; j < i; ++j) {
				f[i][j] = f[i - 1][j] + j;
			}
		} else {
			for (int j = 0; j <= i; ++j) {
				f[i][j] = max(f[i - 1][j] + j, j ? f[i - 1][j - 1] : -inf);
			}
		}
	}
	int ans = -1;
	for (int i = 0; i <= n; ++i) {
		ans = max(ans, f[n][i] + i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
	}
	printf("%d\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

There exists a $$$O(n + m)$$$ solution to this problem.

What will you do if the number of possible values for $$$b_i$$$ is small?

Try some randomized algorithms, like color-coding.

#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 = 3030;

int n, m, a[maxn], b[maxn], c[maxn], d[maxn], e[maxn];

struct BIT {
	int c[maxn];
	
	inline void init() {
		mems(c, -0x3f);
	}
	
	inline void update(int x, int d) {
		for (int i = x; i <= n; i += (i & (-i))) {
			c[i] = max(c[i], d);
		}
	}
	
	inline int query(int x) {
		int res = -1e9;
		for (int i = x; i; i -= (i & (-i))) {
			res = max(res, c[i]);
		}
		return res;
	}
} T[32];

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &b[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &c[i]);
	}
	mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
	int ans = 0;
	for (int _ = 0; _ < 300; ++_) {
		for (int i = 1; i <= n; ++i) {
			d[i] = rnd() % m;
		}
		for (int i = 1; i <= n; ++i) {
			e[i] = d[b[i]];
		}
		for (int i = 0; i < (1 << m); ++i) {
			T[i].init();
		}
		T[0].update(1, 0);
		for (int i = 1; i <= n; ++i) {
			for (int S = 0; S < (1 << m); ++S) {
				if (S & (1 << e[i])) {
					continue;
				}
				T[S | (1 << e[i])].update(a[i], T[S].query(a[i]) + c[i]);
			}
		}
		ans = max(ans, T[(1 << m) - 1].query(n));
	}
	printf("%d\n", ans > 0 ? ans : -1);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

It seems like a joke now...

What is Piggy's optimal strategy?

What does $$$2l \le r$$$ mean?

#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;
}

Consider each bit separately.

Calculate the time when the $$$d$$$-th bit of $$$a_n$$$ becomes $$$1$$$.

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.

#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;
}

#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;
}

Figure out the case where $$$a'_1 \ne -1, a'_n \ne -1$$$ and $$$a'_2 = a'_3 = \cdots = a'_{n - 1} = -1$$$ first.

Imagine a full binary tree. Consider the sequence as a walk on the full binary tree.

#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;
}

$$$a_i$$$ should take different primes.

Transform it into a graph problem.

#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;
}

Stop thinking about Boruvka.

Most of the edges in the graph are useless.

#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;
}

Try some dp that takes $$$O(n^2)$$$ time.

What's the maximum MEX in the optimal good set of paths?

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.

#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;
}

#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 
*/