• D1 was originally proposed as B.
• This round originally had a problem called "Token Moving", but we removed it during the testing phase.

• Amazing:
• Good:
• OK:
• Bad:
• Terrible:

To maximize the $$$\operatorname{mex}$$$, we greedily check non-negative integers $$$i$$$ in ascending order, trying to make each $$$i$$$ the maximum of a subset.

Making $$$i$$$ the maximum requires consuming one element equal to $$$i$$$ and $$$k - 1$$$ other available elements $$$\le i$$$. As $$$i$$$ increases monotonically, the count of available elements $$$\le i$$$ can be maintained dynamically.

Once we reach an $$$i$$$ for which the available elements are insufficient to form a valid subset with maximum $$$i$$$, it means $$$i$$$ cannot appear in the set of subset maximums. Thus, by definition, $$$i$$$ is the maximum possible $$$\operatorname{mex}$$$.

Time complexity per test case: $$$O(n)$$$.

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 105;

int n, k, a, c[N], s;
bool t;

void solve() {
	cin >> n >> k, s = t = 0;
	for(int i = 0; i <= n; ++i) {
		c[i] = 0;
	}
	for(int i = 1; i <= n; ++i) {
		cin >> a, ++c[a];
	}
	for(int i = 0; i <= n; ++i) {
		if(not c[i] or s + c[i] < k) {
			cout << i << '\n';
			return;
		}
		s += c[i] - k;
	}
	return;
}

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

• Amazing:
• Good:
• OK:
• Bad:
• Terrible:

First, let us find out when a sequence $$$b$$$ of length $$$m$$$ is good. If $$$\min(b) = 0$$$, $$$b$$$ is trivially good: we can reduce all other positive elements to $$$0$$$ without ever deleting the $$$0$$$. Otherwise, we keep an element equal to $$$\min(b)$$$ and repeatedly operate on it together with an adjacent element, decreasing it by $$$1$$$ and deleting the adjacent element. Since at most $$$m-1$$$ deletions can be performed while $$$b$$$ stays non-empty, $$$\min(b)$$$ can be reduced to $$$0$$$ if and only if $$$\min(b) \lt m$$$. Therefore, $$$b$$$ is good if and only if $$$\min(b) \lt m$$$.

Now consider the sequence $$$a$$$ of length $$$n$$$. If $$$\min(a) \lt n$$$, then $$$a$$$ itself is good, so the answer is $$$n$$$. Otherwise, every subsequence of length $$$m \le n$$$ has its minimum at least $$$n \ge m$$$, so no good subsequence exists and the answer is $$$0$$$.

Time complexity per test case: $$$O(n)$$$.

#include <bits/stdc++.h>

using namespace std;

int n, a, mn;

void solve() {
	cin >> n, mn = n;
	for(int i = 1; i <= n; ++i) {
		cin >> a, mn = min(mn, a);
	}
	if(mn < n) cout << n << '\n';
	else cout << "0\n";
	return;
}

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

• Amazing:
• Good:
• OK:
• Bad:
• Terrible:

After adding an edge $$$(1,v_i)$$$, consider the path from $$$v_i$$$ to $$$n$$$ in the original tree. If this path passes through vertex $$$1$$$, keeping $$$(1,v_i)$$$ cannot improve the answer, so we simply delete the newly added edge. Otherwise, we keep $$$(1,v_i)$$$ and delete the original edge incident to $$$1$$$ on the path from $$$1$$$ to $$$n$$$; this edge lies on the created cycle. The distance between $$$1$$$ and $$$n$$$ becomes $$$1 + \operatorname{dist}(v_i,n)$$$.

It suffices to use one operation this way and delete the newly added edge in all others. Nothing better is possible: every added edge is incident to $$$1$$$, so a simple path from $$$1$$$ to $$$n$$$ in the final tree uses at most one of them, as its first edge, and then follows an original path from $$$v_i$$$ to $$$n$$$ avoiding $$$1$$$. Therefore, the answer is

Run BFS from vertex $$$n$$$ without expanding vertex $$$1$$$. A vertex is reached exactly when its path to $$$n$$$ does not pass through $$$1$$$, which gives all distances needed by the formula. Remember to reset the distances for each test case.

Time complexity per test case: $$$O(n + m)$$$.

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 500005;

int n, m, d[N], ans;
vector<int> to[N];
queue<int> q;

void solve() {
	cin >> n >> m;
	for(int u = 1; u <= n; ++u) {
		d[u] = -1, to[u].clear();
	}
	for(int _ = 1; _ < n; ++_) {
		int u, v; cin >> u >> v;
		to[u].push_back(v);
		to[v].push_back(u);
	}
	d[n] = 0, q.push(n);
	while(q.size()) {
		int u = q.front();
		q.pop();
		if(u == 1) continue;
		for(int v : to[u]) {
			if(d[v] < 0) {
				d[v] = d[u] + 1;
				q.push(v);
			}
		}
	}
	ans = d[1];
	while(m--) {
		int v; cin >> v;
		ans = max(ans, d[v] + 1);
	}
	cout << ans << '\n';
}

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

• Amazing:
• Good:
• OK:
• Bad:
• Terrible:

Let $$$V = 10^{18}$$$. First, let us consider how to compute $$$f(n)$$$.

Consider a maximal block of $$$k$$$ consecutive type-1 operations; together they add $$$1 + 2 + \dots + 2^{k - 1} = 2^k - 1$$$ to $$$x$$$. If we need to keep operating afterward, the next operation must be a type-2 operation, which resets the counter to zero. Therefore, we can treat these $$$k + 1$$$ operations as a single unit that costs $$$k + 1$$$ and adds $$$2^k - 2$$$ to $$$x$$$.

Now the order of operations no longer matters. We can first perform several such units until $$$x \ge n$$$, and then perform $$$x - n$$$ type-2 operations. Suppose $$$2^k \le n \lt 2^{k + 1}$$$ with $$$k \gt 1$$$. There are two options:

• Perform $$$k$$$ type-1 operations followed by one type-2 operation. The remaining value is $$$n - x = n - 2^k + 2$$$, so the cost is $$$f(n - 2^k + 2) + k + 1$$$.
• Perform $$$k + 1$$$ type-1 operations, then perform $$$2^{k + 1} - 1 - n$$$ type-2 operations and stop. The cost is $$$2^{k + 1} - n + k$$$.

It is easy to show that performing fewer than $$$k$$$ type-1 operations is never better. Hence, for $$$n \lt 4$$$ we have $$$f(0) = 0$$$, $$$f(1) = 1$$$, $$$f(2) = 3$$$, $$$f(3) = 2$$$, and for $$$n \ge 4$$$,

We can compute $$$f(n)$$$ directly with this recursion. Since $$$n$$$ roughly halves at each step, computing $$$f(n)$$$ takes $$$O(\log V)$$$ time, which is enough for the easy version.

Time complexity: $$$O(\sum (r - l + 1) \log V)$$$.

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int mod = 998'244'353;

int l, r, ans;

int f(int n) {
	if(n <= 1) return n;
	if(n == 2) return 3;
	if(n == 3) return 2;
	int k = __lg(n);
	return min(f(n - (1ll << k) + 2) + k + 1, k + (1ll << (k + 1)) - n);
}

void solve() {
	cin >> l >> r, ans = 0;
	for(int i = l; i <= r; ++i) {
		ans += f(i);
	}
	cout << ans % mod << '\n';
	return;
}

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

• Amazing:
• Good:
• OK:
• Bad:
• Terrible:

Let $$$g(n) = \sum \limits_{i = 0}^n f(i)$$$. Then the answer is $$$g(r) - g(l - 1)$$$.

If we always take the first option of the recursion, each unit costs $$$O(\log V)$$$ and there are $$$O(\log V)$$$ levels, so $$$f(n) = O(\log^2 V)$$$. Choose a threshold $$$B = O(\log^2 V)$$$ with $$$B \gt \max f(i)$$$. For any $$$n \in [2^k, 2^{k + 1} - B]$$$, the second option costs $$$2^{k + 1} - n + k \gt f(n)$$$, so it is never optimal, and therefore $$$f(n) = f(n - 2^k + 2) + k + 1$$$. In other words, the second option only matters for the last fewer than $$$B$$$ values of each interval $$$[2^k, 2^{k + 1})$$$.

Using this, we can compute $$$g(n)$$$ piece by piece. Let $$$2^k \le n \lt 2^{k + 1}$$$ and $$$w = \max(2^k - 1, \min(n, 2^{k + 1} - B))$$$ (the outer $$$\max$$$ only matters for small $$$k$$$, where the whole interval lies beyond the threshold). Then

For the last term, note that $$$n - w = O(\log^2 V)$$$. So for each $$$k$$$ we precompute $$$f$$$ and its prefix sums at all positions in $$$(2^{k + 1} - B, 2^{k + 1})$$$. This is $$$O(\log^3 V)$$$ values of $$$f$$$ in total, each computed in $$$O(\log V)$$$, so this part takes $$$O(\log^4 V)$$$ time.

The values $$$g(2^k - 1)$$$ and $$$g(2^k - B + 2)$$$ only depend on smaller values of the same two forms, so we can precompute all of them in increasing order of $$$k$$$.

Now for a query $$$g(n)$$$, apply the formula above. If $$$w = 2^{k + 1} - B$$$, then $$$g(w - 2^k + 2) = g(2^k - B + 2)$$$ is already precomputed and we are done. Otherwise, $$$w = n$$$, and we recurse into $$$g(n - 2^k + 2)$$$, where $$$n - 2^k + 2 \lt 2^k$$$, so the highest bit strictly decreases. Hence the recursion depth is $$$O(\log V)$$$, and each query takes $$$O(\log V)$$$ time.

Time complexity: $$$O(\log^4 V + t \log V)$$$.

Bonus

The threshold can be made exact. Appending one type-2 operation shows $$$f(n) \le f(n + 1) + 1$$$, so $$$h(n) = f(n) + n$$$ is non-decreasing. With $$$m = n - 2^k + 2$$$, the first option of the recursion is optimal if and only if $$$f(m) + k + 1 \le 2^{k + 1} - n + k$$$, that is, $$$h(m) \le 2^k + 1$$$. Hence the valid values of $$$m$$$ form a prefix; let $$$\mathrm{pos}_k$$$ be its last element. Then $$$f(n) = f(n - 2^k + 2) + k + 1$$$ for $$$n \in [2^k, \mathrm{pos}_k + 2^k - 2]$$$, and $$$f(n) = 2^{k + 1} - n + k$$$ for the rest of the interval. Since the valid values form a prefix, $$$\mathrm{pos}_k$$$ can be found by binary search, which takes $$$O(\log^3 V)$$$ in total.

The rest is the same as before, except that the part beyond the threshold is now an arithmetic progression and can be summed in $$$O(1)$$$. Let $$$w = \min(n, \mathrm{pos}_k + 2^k - 2)$$$. Then

We precompute $$$g(2^k - 1)$$$ in increasing order of $$$k$$$ as before. The term $$$g(w - 2^k + 2)$$$ does not even need precomputation. Since $$$f(m) \ge 2$$$ for $$$m \ge 2$$$, we have $$$h(m) \ge m + 2$$$, so $$$\mathrm{pos}_k \le 2^k - 1$$$ and thus $$$w - 2^k + 2 \lt 2^k$$$. Hence we can compute it recursively: each call makes only one recursive call and the highest bit strictly decreases, so the recursion depth is $$$O(\log V)$$$.

Time complexity: $$$O(\log^3 V + t \log V)$$$.

Computing $$$\mathrm{pos}_k$$$ in $$$O(\log V)$$$

Recall that $$$\mathrm{pos}_k$$$ is the largest $$$m$$$ with $$$h(m) = f(m) + m \le 2^k + 1$$$. Let a type-1 operation that adds $$$2^j$$$ cost $$$2^j + 1$$$, and let a type-2 operation be free. Every step then costs $$$1$$$ plus the change of $$$x$$$, so the minimum cost to reach $$$n$$$ is exactly $$$h(n)$$$, and $$$\mathrm{pos}_k$$$ is the largest $$$x$$$ reachable with budget $$$2^k + 1$$$.

A maximal block of $$$i$$$ type-1 operations adds $$$2^i - 1$$$ and costs $$$2^i + i - 1$$$. In an optimal solution, all blocks have distinct lengths: two blocks of length $$$j \ge 2$$$ can be merged into one block of length $$$j + 1$$$, which gives a larger $$$x$$$ at no extra cost, and a block of length $$$1$$$ other than the first one only cancels the type-2 operation before it. Now let $$$i$$$ be the largest length that fits into the budget. If every block were shorter than $$$i$$$, we would get $$$x \le \sum_{j = 1}^{i - 1} (2^j - 1) \lt 2^i - 1$$$, which is worse than a single block of length $$$i$$$. So the longest block has length exactly $$$i$$$, and we repeat the argument with the remaining budget.

Therefore, we go through $$$i = k, k - 1, \ldots, 2$$$ and take a block of length $$$i$$$ whenever its cost $$$2^i + i - 1$$$ fits into the remaining budget. The first block adds $$$2^i - 1$$$, and every later one, together with the type-2 operation before it, adds $$$2^i - 2$$$, so $$$\mathrm{pos}_k = 1 + \sum (2^i - 2)$$$ over the chosen $$$i$$$. This takes $$$O(\log V)$$$ for each $$$k$$$, so the precomputation now takes only $$$O(\log^2 V)$$$ time.

Time complexity: $$$O(\log^2 V + t \log V)$$$.

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int mod = 998'244'353;
constexpr int inv2 = (mod + 1) >> 1;

int l, r, pos[60], val[60];

int g(int n) {
	if(n <= 1) return max(n, 0ll);
	int k = __lg(n), w = min(n, pos[k] + (1ll << k) - 2), res = 0;
	res = val[k];
	res = (res + g(w - (1ll << k) + 2) + mod - 1 + (w - (1ll << k) + 1) % mod * (k + 1)) % mod;
	res = (res + ((1ll << (k + 2)) + 2 * k - w - n - 1) % mod * ((n - w) % mod) % mod * inv2) % mod;
	return res;
}

void solve() {
	cin >> l >> r;
	cout << (g(r) + mod - g(l - 1)) % mod << '\n';
	return;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	for(int k = 0; k < 60; ++k) {
		int lft = (1ll << k) + 1;
		pos[k] = 1;
		for(int i = k; i >= 2; --i)
			if((1ll << i) + i - 1 <= lft)
				lft -= (1ll << i) + i - 1, pos[k] += (1ll << i) - 2;
		val[k] = g((1ll << k) - 1);
	}
	int T = 1; cin >> T;
	while(T--) solve();
	return 0;
}

• Amazing:
• Good:
• OK:
• Bad:
• Terrible:

Root the tree at vertex $$$1$$$. First, we find the subtree size $$$siz_i$$$ of every vertex. Clearly $$$siz_1 = n$$$. For each $$$i \gt 1$$$, make a query with $$$x = 1$$$, $$$p_1 = n-1$$$, $$$p_i = n$$$, and the remaining values assigned arbitrarily. If $$$j$$$ lies in the subtree of $$$i$$$, the path from $$$j$$$ to $$$1$$$ passes through $$$i$$$, so its contribution is $$$n$$$; otherwise it is $$$n-1$$$. Hence the query returns $$$n(n-1) + siz_i$$$. This step uses $$$n-1$$$ queries.

Next, to reconstruct the tree, sort all vertices in decreasing order of $$$siz$$$, and let the sorted order be $$$a_1, a_2, \ldots, a_n$$$. Since an ancestor always has a strictly larger subtree than its descendants, the parent of $$$a_i$$$ must be among $$$a_1, a_2, \ldots, a_{i-1}$$$.

Suppose we already know the structure of the subtree formed by $$$a_1, a_2, \ldots, a_{i-1}$$$. We now add $$$a_i$$$ and find its parent with a single query.

Construct the query as follows: set $$$x = a_i$$$ and $$$p_{a_i} = 1$$$. Order the already known vertices by depth in increasing order (e.g., using BFS), and assign the value $$$k+1$$$ to the $$$k$$$-th vertex in this order. Finally, for each $$$j \gt i$$$, set $$$p_{a_j} = j$$$.

Why does this work? For $$$j \gt i$$$, every vertex on the path from $$$a_j$$$ to $$$a_i$$$ other than $$$a_j$$$ itself is either an ancestor of $$$a_j$$$ or of $$$a_i$$$, and thus has an index smaller than $$$j$$$; so the contribution of $$$a_j$$$ is exactly $$$j$$$, and the total contribution of these vertices is the constant $$$\sum_{j=i+1}^n j$$$. The contribution of $$$a_i$$$ itself is $$$1$$$. For the known part, let $$$f$$$ be the parent of $$$a_i$$$. Since values strictly increase with depth, the maximum on the path from a known vertex $$$v$$$ to $$$a_i$$$ is $$$\max(p_v, p_f)$$$, so the total contribution is $$$\sum_{k=1}^{i-1} \max(p_f, k+1)$$$. This is strictly increasing in $$$p_f$$$ for $$$2 \le p_f \le i$$$, so the answer determines $$$f$$$ uniquely. Thus this step uses another $$$n-1$$$ queries, for a total of $$$2n-2$$$.

Time complexity per test case: $$$O(n^2)$$$.

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 505;

int n, sz[N], p[N], a[N], cur, res, tmp;
vector<int> to[N];
queue<int> q;

int query(int x, int *p) {
	cout << "? " << x;
	for(int u = 1; u <= n; ++u) {
		cout << ' ' << p[u];
	}
	cout << endl;
	int res; cin >> res;
	return res;
}

void solve() {
	cin >> n;
	p[1] = n, p[2] = n - 1;
	for(int u = 3; u <= n; ++u) {
		p[u] = u - 2;
	}
	for(int u = 2; u <= n; ++u) {
		swap(p[u - 1], p[u]);
		sz[u] = query(1, p) - n * (n - 1);
		a[u] = u;
	}
	a[1] = 1;
	sort(a + 2, a + n + 1, [](int u, int v) {
		return sz[u] > sz[v];
	});
	for(int i = 2; i <= n; ++i) {
		cur = 1;
		q.push(1);
		while(q.size()) {
			int u = q.front();
			q.pop();
			p[u] = ++cur;
			for(int v : to[u]) {
				q.push(v);
			}
		}
		p[a[i]] = 1;
		for(int j = i + 1; j <= n; ++j) {
			p[a[j]] = j;
		}
		res = query(a[i], p);
		res -= (i + 1 + n) * (n - i) / 2 + i;
		for(int j = 1; j < i; ++j) {
			tmp = p[a[j]] - 1;
			if(res == tmp * (i - 1) + (i - tmp) * (i - tmp - 1) / 2) {
				to[a[j]].push_back(a[i]);
			}
		}
	}
	cout << "!\n";
	for(int u = 1; u <= n; ++u) {
		for(int v : to[u]) {
			cout << u << ' ' << v << '\n';
		}
		to[u].clear();
	}
	fflush(stdout);
	return;
}

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

• Amazing:
• Good:
• OK:
• Bad:
• Terrible:

Fix a root $$$r$$$. If a proper ancestor of $$$u$$$ is operated on before $$$u$$$, all tokens of the subtree of $$$u$$$ have already been moved out, so the operation on $$$u$$$ costs $$$0$$$. Otherwise, it costs the initial token sum of the subtree of $$$u$$$, since earlier operations only moved tokens inside this subtree. In the second case, we say that $$$u$$$ \textit{contributes} to $$$r$$$.

Thus, $$$u$$$ contributes to $$$r$$$ if and only if no vertex on the path from $$$u$$$ to $$$r$$$ is operated on before $$$u$$$. Equivalently, if we delete all vertices operated on before $$$u$$$, then $$$u$$$ contributes exactly to the vertices of its connected component.

Let $$$S$$$ be the total number of tokens. If $$$r = u$$$, the contribution is $$$S$$$. Otherwise, let $$$v$$$ be the neighbor of $$$u$$$ on the path from $$$u$$$ to $$$r$$$, and let $$$W(u, v)$$$ be the token sum of the part containing $$$v$$$ after removing the edge $$$(u, v)$$$. The subtree of $$$u$$$ is the other part, so the contribution is $$$S - W(u, v)$$$. Note that it depends only on $$$v$$$, not on $$$r$$$.

Instead of deleting vertices, we add them in the order $$$p_n, \ldots, p_1$$$ and use a DSU to build a reconstruction tree: when adding $$$u$$$, we make the root of each adjacent active component a child of $$$u$$$ and merge the components. The reconstruction subtree of $$$u$$$ is then exactly the component to which $$$u$$$ contributes, and the whole tree is rooted at $$$p_1$$$. Moreover, the subtree of the child created through an edge $$$(u, v)$$$ consists of exactly the vertices reached from $$$u$$$ through $$$v$$$.

Now consider the answer for $$$r$$$. The vertices contributing to $$$r$$$ are exactly $$$r$$$ and its ancestors in the reconstruction tree. The vertex $$$r$$$ itself gives $$$S$$$. Each ancestor $$$u$$$ gives $$$S - W(u, v)$$$, where $$$(u, v)$$$ is the edge that created the child $$$c$$$ of $$$u$$$ on the path to $$$r$$$. So when attaching $$$c$$$ to $$$u$$$, we assign the value $$$S - W(u, v)$$$ to $$$c$$$. Then the answer for $$$r$$$ is $$$S$$$ plus the sum of the values on the path from $$$p_1$$$ to $$$r$$$, and a single DFS from $$$p_1$$$ computes these sums for all $$$r$$$ in $$$O(n)$$$.

To compute $$$W(u, v)$$$, root the original tree arbitrarily and compute the subtree sums $$$\mathit{sub}_x$$$. Then $$$W(u, v) = S - \mathit{sub}_u$$$ if $$$v$$$ is the parent of $$$u$$$, and $$$W(u, v) = \mathit{sub}_v$$$ otherwise, so each $$$W(u, v)$$$ is obtained in $$$O(1)$$$.

Time complexity per test case: $$$O(n \log n)$$$ or $$$O(n \alpha(n))$$$.

#include <bits/stdc++.h>

using namespace std;

constexpr int mod = 998'244'353;
constexpr int N = 500005;

void M(int &x) { x -= (x >= mod ? mod : 0); }

int n, a[N], p[N], fa[N], ans[N], tmp;
vector<int> to[N], nto[N];
bool vis[N];

struct DSU {
	int fa[N];
	void init(int n) {
		for(int x = 1; x <= n; ++x) {
			fa[x] = x;
		}
	}
	int find(int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);
	}
	void merge(int x, int y) {
		x = find(x), y = find(y);
		if(x == y) return;
		fa[x] = y;
	}
} dsu;

void dfs1(int u) {
	for(int v : to[u]) {
		if(v != fa[u]) {
			fa[v] = u, dfs1(v);
			M(a[u] += a[v]);
		}
	}
}

void dfs2(int u) {
	for(int v : nto[u]) {
		M(ans[v] += ans[u]);
		dfs2(v);
	}
}

void solve() {
	cin >> n;
	for(int u = 1; u <= n; ++u) {
		to[u].clear(), nto[u].clear(), ans[u] = 0;
	}
	for(int _ = 1; _ < n; ++_) {
		int u, v; cin >> u >> v;
		to[u].push_back(v);
		to[v].push_back(u);
	}
	for(int u = 1; u <= n; ++u) {
		cin >> a[u];
	}
	for(int i = 1; i <= n; ++i) {
		cin >> p[i];
	}
	dfs1(1);
	dsu.init(n);
	for(int u = 1; u <= n; ++u) {
		vis[u] = 0;
	}
	for(int i = n; i; --i) {
		int &u = p[i];
		for(int v : to[u]) {
			if(vis[v]) {
				if(v == fa[u]) {
					v = dsu.find(v);
					M(ans[v] += a[u]);
				} else {
					M(tmp = a[1] + mod - a[v]);
					v = dsu.find(v);
					M(ans[v] += tmp);
				}
				nto[u].push_back(v);
				dsu.merge(v, u);
			}
		}
		vis[u] = 1;
	}
	M(ans[p[1]] += a[1]), dfs2(p[1]);
	for(int u = 1; u <= n; ++u) {
		cout << ans[u] << " \n"[u == n];
	}
	return;
}

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

• Amazing:
• Good:
• OK:
• Bad:
• Terrible: