Thank you for participating in the round!
- D1 was originally proposed as B.
- This round originally had a problem called "Token Moving", but we removed it during the testing phase.
Author: Getaway_Car
Check the values $$$0, 1, 2, \ldots$$$ in increasing order. What is needed for $$$i$$$ to be the maximum of some multiset?
A multiset with maximum $$$i$$$ needs one element equal to $$$i$$$ and $$$k - 1$$$ other elements not exceeding $$$i$$$. An element that is not used now can still be used for any larger value, so keep track of how many such elements are available.
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;
}
Author: Getaway_Car
First, find out when a sequence $$$b$$$ of length $$$m$$$ is good. Which element would you try to reduce to $$$0$$$?
Each operation deletes one element, so at most $$$m - 1$$$ operations can be performed while $$$b$$$ stays non-empty. Compare $$$\min(b)$$$ with $$$m$$$.
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;
}
Author: _O_v_O_
Every added edge is incident to vertex $$$1$$$. How many added edges can a simple path from $$$1$$$ to $$$n$$$ in the final tree use?
If you decide to keep the edge $$$(1, v_i)$$$, which original edge should you delete? When is keeping it useless?
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;
}
2277D1 - Number Operating (Easy Version)
Author: Getaway_Car
Group a maximal block of consecutive type-1 operations together with the type-2 operation right after it. How much does such a unit cost, and how much does it add to $$$x$$$? Does the order of the units matter?
Let $$$2^k \le n \lt 2^{k + 1}$$$. It is enough to consider a first block of either $$$k$$$ or $$$k + 1$$$ type-1 operations. This gives a recursion for $$$f(n)$$$.
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;
}
2277D2 - Number Operating (Hard Version)
Author: Getaway_Car
We'd like to thank RockyYue for providing an optimized solution.
Use the recursion from the easy version. How large can $$$f(n)$$$ be?
Since $$$f(n)$$$ is small, the second option of the recursion can only be optimal for the last few values of each interval $$$[2^k, 2^{k + 1})$$$.
Let $$$g(n) = \sum_{i = 0}^n f(i)$$$. On the part of $$$[2^k, 2^{k + 1})$$$ where the first option is always optimal, express the sum of $$$f$$$ through $$$g$$$ at a smaller argument.
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;
}
Author: _O_v_O_
Root the tree at vertex $$$1$$$. Can you find the size of every subtree with $$$n - 1$$$ queries?
Sort the vertices by subtree size in decreasing order. The parent of each vertex appears before it. Try to find the parent of each vertex with a single query.
Give the vertices already placed in the tree values that increase with depth, and give the vertex being added the smallest value.
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;
}
Author: Getaway_Car
Fix the root $$$r$$$. When does the operation on $$$u$$$ have a non-zero cost, and what is the cost in that case?
The operation on $$$u$$$ has a non-zero cost exactly when no vertex on the path from $$$u$$$ to $$$r$$$ is operated on before $$$u$$$. Try adding the vertices in the reverse order of $$$p$$$ and maintaining the components with a DSU.
In that case, the cost depends only on the neighbor of $$$u$$$ in the direction of $$$r$$$, not on $$$r$$$ itself.
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;
}








Auto comment: topic has been updated by Getaway_Car (previous revision, new revision, compare).
if D1 was b then it is not fun fact but horror fact :p
I feel like d1 was a bit easier compared to most other div2 d's. Nice round tho!
Yes easy for ai cheaters https://codeforces.me/submissions/CocoCat/contest/2259
where easier?
Oh wow thats highkey surprising. I usually solve div2d but couldn't figure this one out
Why is problem E and F easier than problem D
D2 is much harder than E...
I figured out the recursion for d1 in log n but i didnt understand how to do it for 10e18, ik we have to like reuse some values but couldnt understand edu
Why do you need to store values when max tree depth is only 60?
I wish I could participate but gotta study bio for my bio exams in 2 weeks :/
I don't like trees, so I skipped C and went straight to D, only to get stuck there :(
I'm wrong, C is very interesting!
I had studied but still able to solve till C...!!
a-c is good!
man you are in IIT and still cheating don't cheat brother enjoy the game
https://codeforces.me/contest/2277/submission/395844945
good job bro seems like u had enough time to write comments too
Yeah because I save the solutions in a file,and for majority of problems that i find good i write comments.also i had enough time beacuse i just had to solve 3-4 questions.just quite ew times when i am able to draw soln. but unable to code in such cases i explain my soln. to AI,which gives me code in written(just some beginner level things)
ur not fooling anyone bud just yourself
sandbox:/mnt/data/image(20261024-180525).png
linux better btw
Worst I've seen someone rat themselves out with less than 50 characters
Lets see in future buddy!!!....just remember me!!!
no buddy you just exposed yourselves for using ai in a contest ur getting banned soon
No buddy i dont fear it...If I get,i shall restart again...See u then...
i dont care cheat as much as you want, iit kharagpur already has a bad past/repo on codeforces u can feed the stereotypes for all i care
WE SHALL SEE THAT
fast editorial!
A is damn hard...
speedblitz edu :O
fast editorial!!
in q c. i did by using dsu path compression as i dont know how to do binary uplifting. we can obervse that any node say x then if x and n have lca other than 1 it can make path longer . so if their lca is not 1 its useful to us.so i use dsu path compression to store par of everyone either its 1 or other (i stored a path from 1 to n in a set and now i stored everyone par as 1 of member of this set) now. for every vertex that we are given to explore. i just see if the par is not 1. then just used that formula . 1+depth(n)-2*depth(common lca)+depth(j).its not the best approach but i am happy first time i solved q. c in contest.
There exists an easier method as well using DFS.
The operations boil down to "Select a single node (say x) from the m operations and add an edge (1, x) and delete the first edge in the path from node 1 to node n". Upon doing this, the distance between 1 and n is [dist(x, n) + 1]. However this won't work when node m and node n are in separate subtrees of the root. If they are in separate subtrees, then you can't remove the first edge of path(1 -> n) since n would be unreachable. So in that case the distance is always dist(1, n) so there's no point in doing anything.
So TLDR; You can get the distances between node N and all other nodes using DFS and then you need to go over all the operations and if node m is in the same side as node N, you can do ans = max(ans, dist[m] + 1). Submission: https://codeforces.me/contest/2277/submission/395867370
could anyone tell me whats wrong with my solution for A 395842509
I dealed with your submission and found that it gives WA for the following :
1 5 2 0 0 0 1 2Because that you are missing to set your
mp[i]variable to 0 when it is insufficient to form a set with max elementi.Solution : Just write
mp[i] = 0before the last if statement (req > 0 part) in your nested loop. You can check my submissions also.oh yes, thank you
Problem B is confusing. First the problem says, "3. choose one element of this subarray and remove it from b, without changing the order of the remaining elements."
And then in the 4-th testcase,
5 // 2 1 1 0 3the output is5. The tutorial assumes that we only can reduce the elements and skip the removal part! What's going on?NOTE: I can be wrong, please explain your point simply! Tnx!
We can show that 5 works here; by choosing entire array, our first operation can be solely the final element which makes the array 2110 (since 3 is removed), from there we can choose [1,3] at whcih the array can be 000 since it goes 2110->1000->000. I think this is how it might go?
According to the output requirements: "output a single integer — the maximum length of a good subsequence of
a, or0if no such subsequence exists", shouldn't the ans be3instead? Then to all those people who solved it, how did they knew the question has errors?No the answer is 5. Maximum length is number of elements in the longest subsequences that is good, NOT the largest value of a good subsequence. The question did not have error(s).
UH!!!!! Got it at last! Many thanks!
They haven't specified the size of the subarray we have to choose in the qs. So since there is already a 0 present in the subarray, we can just take our "good" subsequence as 2 1 1 0 3 and then perform 4 ops on each of the individual elements.
Take [2] for instance, after 1 op it becomes [1] but we have to remove one element also so it becomes []. Do this for all the other ai > 0. so our final array is just [0]
We can just extend this idea to the case where we don't have a 0 at all in the array. In general if theres at least one element <= n — 1, we can make the whole array "good".
I mean, one could only reduce an array's size after removing some elements from it?
For the testcase, You can select the full array as a sub-sequence and test if it's good or not.
[2 1 1 0 3] For making this good, select the [2 1 1] as a subarray and do the subtractions, becomes: [1 0 0] and remove an element, let's remove 1 becomes: [0 0] + [0 3] = [0 0 0 3]
Then select [3] as a subarray, decrement to get [2] and remove an element to get []
[0 0 0] + [] = [0 0 0] As you can see, we have boiled the array down to a non-empty array consisting purely of zeros. So this subsequence is good and because it is the largest subsequence, it is also the answer.
To make the process easy, you could start by asking:
If there's at least 1 zero in an array, can I always make the array good?
Take the whole array, reduce it to good array and read the problem statement again. Thank you.
Ah, yes. The problem boils down to if the array constains a number
< n. 395889805The question is weather this array can be transformed into an array consisting of only zeros or not even if after removing everything and only 1 zero this means that the size of current array is the answer in the example you showed we can remove every element and leave the 0 and that would mean we made it from this array to an array with '0' so this array of size 5 is valid, sorry if i don't make sense you should re-read the problem that might help
I am too weak :(
I'm weak too. Let's be friends!
ok,i'm happy
nahh bro a was cruel
My solution discussion stream for ABCD1E
My Question to the people who were able to do D1:
How can you be sure during the contest that these two ways were sufficient, and there is no other way of 0 -> (operations) -> n, which gives a more optimal answer ?
Based on my prior experiences, whenever I find two ways of doing a thing and drawing cases show that for some cases first way gives correct answer and for some cases the second way, the general tendency of mine is to take the best of these two ways just to get a WA on test 2. Unfortunately, I did not even try minimising both definitions of f(n) i wrote, during the contest, and later found out that it was indeed the optimal solution.
Wait that was intended, i took a completely different path than yours that requried way more guessing. My subimission:395865736
If you observe f(i) from 1 to 30, you may guess it is correct
Yes, I did something similar, do manual f(i) for i (1 to 32), the reason it's more optimal is because of the way exponents grow. you would never want to build 9 using 3 3s but by using 7 + 3.
in D1 i mistakenly read it as (where k is the number of type 2 operations you have performed before) so i just got stuck then i read F and i thought on it got a very long implementation solution started implementing but got time out.
We notice that operations can be alternating, and we will compress operations into adding $$$2^k - 2$$$ with a cost of $$$k$$$. Handle odd numbers by just setting their cost to $$$\min(\texttt{cost}_{n-1} - 1, \texttt{cost}_{n+1} + 1)$$$ with the exception of $$$\texttt{cost}_1 = 1$$$. Now for even numbers, we can brute force on the amount of blocks of 1 operations used. Now we will cover how to check the cost of using a certain number of operations.
Let $$$n$$$ be the target number, $$$k$$$ be the number of grouped operations, and $$$x = n + 2k$$$. We can only get there if $$$\operatorname{popcount}(x) \leq k$$$. We will count the minimum number of operations to get to $$$x$$$ using the following operation: add $$$2^m$$$ with a cost of $$$m$$$. Obviously, this will be equal to the "weighted popcount" of $$$x$$$: add $$$1$$$ if the 1st bit is on, $$$2$$$ if the 2nd bit is on, $$$3$$$ if the 3rd bit is on... Additionally, we need to consider the cost of subtraction operations and redundant operations, so the final cost will be $$$\operatorname{wpopcount}(x) + 2k - \operatorname{popcount}(x)$$$.
For a target number $$$n$$$, what $$$x$$$ values (as previously defined) should we check? It turns out that for every popcount that doesn't overflow $$$i$$$, we can check the minimum even number $$$\geq n + 2i$$$ with a popcount of $$$i$$$. This works since for any greater number with the same popcount, it will incur more cost either from being greater or having a larger weighted popcount. We can generate these with a standard top-to-bottom greedy approach.
Since the operation checker function takes $$$O(\log N)$$$ time to run, and we check $$$O(\log N)$$$ target values, the solution runs in $$$O(n \log^2 N)$$$, which barely passes, so languages other than C++ may be difficult/impossible to AC in. C++ implementation that passes in 80% of the TL: 395871664
Such a cool round!
Does someone have a proof for why exactly is 1 type-2 operation optimal, as in it was natural to guess this. But is there a solid proof of why it is optimal.
Why can't something like (k + 2 + f(n — 2^k + 3)) be optimal.
Thank you
If we perform a second type-2 operation immediately, we spend one extra move and increase our target from a to a+1.
but instead, we can solve a+1 optimally and then subtract 1 at the end to reach a. So, f(a) <= f(a+1)+1 Adding a+1 to both sides gives
(k+1)+f(a) <= (k+2)+f(a+1) This means doing extra subtractions upfront cannot give us a better answer. We can simply perform the necessary reset once and let f decide the best time to subtract later.
Wow that's nice, thankss
yw :)
(a small typo is there, we are adding k+1 to both the sides, not a+1)
C is an awesome problem
From D1 editorial: "It is easy to show that performing fewer than k type-1 operations is never better."
I do not understand why. Can someone show this?
"It is easy to show that performing fewer than k type-1 operations is never better" -- from D1's editorial
Is there some clever way to see this? Intuitively, this feels right, but I'm not able to flesh it out
I guess something like this would work:
Suppose you want to find f(k). Let
Consider less than p consecutive applications (say, p-r) of Operation 1, followed by 1 Operation 2.
The recursion in this case is:
And with p consecutive applications, it is,
We can probably prove the expression below is <= the expression above (might be easier to show for r = 1, and the result for general r would follow)
The way I approached the problem is splitting the operations into blocks of operation 1, operation 2, operation 1 etc. It is then easy to see that the order of the blocks of operation 1 do not matter — only their size does. Thus we can rearrange them to prioritise the block with highest number of operation 1 first. Similarly, you can try to prove it is suboptimal to have 2 blocks with same number of operation 1.
I fked up but very interesting problems
is my life cooked a is cooked. how do u guys approach a :( i thought sprting wud do it, but realised it might skip a integer, as in that window of length k, u might have bigger nums, so use the smaller ones for assisstance but wtf that took time to get it helpppppppppp
I don't believe D2 is 2300-2400. I think at minimum it's 2800. Crazy to think, that something like that is considered pretty standart for lgms to implement.
I agree with u!
Hi, why can’t I see other people’s submissions? It just shows “N/A.”
cause ur cheater
Damn this was so hard for me, didn't solve a single one TT
Proof for the recurrence in D:
For a fixed sequence, let:
Two different runs must have at least one type-2 operation between them, otherwise they would merge into one run. So $$$s \ge t-1$$$. Apart from that, the order of operations does not matter, because $$$x$$$ is allowed to go negative. The final value and the cost are:
From the first equation, S=n+s+t. Substituting this into the cost and into s>=t-1 gives:
So $f(n)$ is the minimum of $$$C$$$ over all multisets $$$\lbrace a_1,\dots,a_t \rbrace$$$ satisfying $$$(*)$$$. Here $$$g(a) = a + 2^a - 1$$$ is strictly increasing and positive.
Let $$$k = \lfloor \log_2 n \rfloor$$$, so $$$2^k \le n \lt 2^{k+1}$$$. Take an optimal solution for $$$n \ge 4$$$. Take t>=2
(a) There are no runs of length $$$1$$$ (when $$$t \ge 2$$$). Deleting a run of length $$$1$$$ changes $$$S$$$ by $$$-2$$$ and $$$t$$$ by $$$-1$$$. The right side $$$n + 2t - 1$$$ also changes by $$$-2$$$, so $$$(*)$$$ is unchanged. The cost $$$C$$$ drops by $$$g(1) = 2$$$, hence ,as the cost is getting minimised ,we will delete all runs of length 1.
(b) Equal runs can be merged , therefore in the end we will have all distinct. Replace two runs of length $$$a \ge 2$$$ by one run of length $$$a+1$$$:
(c) The longest run $$$M = \max_i a_i$$$ satisfies $$$M \ge k$$$. Suppose $$$M \le k-1$$$. The lengths are distinct and lie in $$$[2, k-1]$$$, so
which violates (*)
The max run value is either a lone run of length k+1, or exactly k
Consider the single run of length $k+1$ with nothing else, so $$$t = 1$$$ and $$$S = 2^{k+1}$$$. It is feasible because $$$2^{k+1} \ge n+1$$$, and its cost is $$$g(k+1) - n = 2^{k+1} - n + k$$$. This is the second term of the formula. - If $$$M = k+1$$$ and $$$t \ge 2$$$: the other runs add $$$g(a_i) \gt 0$$$, so $$$C = g(k+1) - n + \sum_{\text{other runs}} g(a_i) \gt g(k+1) - n$$$. Again this is strictly worse than the single run. Note that we didn't take M>=k+2 ,because that would ruin our cost function ,compared to M=k+1. Combined with (c), the optimum is either the lone run of length $$$k+1$$$ (the second term), or a solution with $$$M = k$$$, meaning it contains a run of length $$$k$$$.
Nice problems A-D. By the way, the "Bonus" solution with binary search gives $$$O(\log^2 V \log \log V + t \log V)$$$ time, because we need to binary search over a range of length $$$O(\log^2 V)$$$.
you're right
Is this normal? 395868142
I want to practice more problems similar to CF 2277D1, where the core challenge is not implementing DP but discovering the correct recurrence equation from the given operations.
When I search for terms like recurrence relations or recurrence problems, I usually end up finding DP problems, where the state transition is already obvious. However, that's not the skill I'm trying to improve.
i felt b easier than a
cool round rly liked d1 & c(even tho came up with a solution for c after the contest) <3. first task was however annoyingly confusing imo.
D1 and D2 problem, my approach: https://codeforces.me/blog/entry/158156
F can also be solved by processing earlier vertices after later ones and keeping track of their contribution to other vertices: 396325336
Cool round & fast editorial :))) IMO: A is a bit harder than B (still, good thing D1 was not B). C was awesome.
wasn't able to finish C during the contest cuz A somehow took 1.5 hours for me :(((
Hey I stuck at D1 for an hour and a half.