codeforces-scrape

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

2277.md (24164B)


      1 Source: https://codeforces.com/blog/entry/158113
      2 
      3 Thank you for participating in the round!
      4 
      5 **Fun facts**
      6 
      7 * D1 was originally proposed as B.
      8 * This round originally had a problem called "Token Moving", but we removed it during the testing phase.
      9 
     10 **Rate this round**
     11 
     12 * Amazing:
     13 * Good:
     14 * OK:
     15 * Bad:
     16 * Terrible:
     17 
     18 [2277A - Subset Selecting](/contest/2277/problem/A "Codeforces Round 1129 (Div. 2)")
     19 
     20 Author: [Getaway_Car](/profile/Getaway_Car "Master Getaway_Car")
     21 
     22 **Hints**
     23 
     24 **Hint 1**
     25 
     26 Check the values $0, 1, 2, \ldots$ in increasing order. What is needed for $i$ to be the maximum of some multiset?
     27 
     28 **Hint 2**
     29 
     30 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.
     31 
     32 **Tutorial**
     33 
     34 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.
     35 
     36 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.
     37 
     38 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}$.
     39 
     40 Time complexity per test case: $O(n)$.
     41 
     42 **Code**
     43 
     44 ```
     45 #include <bits/stdc++.h>
     46 
     47 using namespace std;
     48 
     49 constexpr int N = 105;
     50 
     51 int n, k, a, c[N], s;
     52 bool t;
     53 
     54 void solve() {
     55 	cin >> n >> k, s = t = 0;
     56 	for(int i = 0; i <= n; ++i) {
     57 		c[i] = 0;
     58 	}
     59 	for(int i = 1; i <= n; ++i) {
     60 		cin >> a, ++c[a];
     61 	}
     62 	for(int i = 0; i <= n; ++i) {
     63 		if(not c[i] or s + c[i] < k) {
     64 			cout << i << '\n';
     65 			return;
     66 		}
     67 		s += c[i] - k;
     68 	}
     69 	return;
     70 }
     71 
     72 int main() {
     73 	ios::sync_with_stdio(0);
     74 	cin.tie(0), cout.tie(0);
     75 	int T = 1; cin >> T;
     76 	while(T--) solve();
     77 	return 0;
     78 }
     79 ```
     80 
     81 **Rate the problem**
     82 
     83 * Amazing:
     84 * Good:
     85 * OK:
     86 * Bad:
     87 * Terrible:
     88 
     89 [2277B - Sequence Decreasing](/contest/2277/problem/B "Codeforces Round 1129 (Div. 2)")
     90 
     91 Author: [Getaway_Car](/profile/Getaway_Car "Master Getaway_Car")
     92 
     93 **Hints**
     94 
     95 **Hint 1**
     96 
     97 First, find out when a sequence $b$ of length $m$ is good. Which element would you try to reduce to $0$?
     98 
     99 **Hint 2**
    100 
    101 Each operation deletes one element, so at most $m - 1$ operations can be performed while $b$ stays non-empty. Compare $\min(b)$ with $m$.
    102 
    103 **Tutorial**
    104 
    105 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$.
    106 
    107 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$.
    108 
    109 Time complexity per test case: $O(n)$.
    110 
    111 **Code**
    112 
    113 ```
    114 #include <bits/stdc++.h>
    115 
    116 using namespace std;
    117 
    118 int n, a, mn;
    119 
    120 void solve() {
    121 	cin >> n, mn = n;
    122 	for(int i = 1; i <= n; ++i) {
    123 		cin >> a, mn = min(mn, a);
    124 	}
    125 	if(mn < n) cout << n << '\n';
    126 	else cout << "0\n";
    127 	return;
    128 }
    129 
    130 int main() {
    131 	ios::sync_with_stdio(0);
    132 	cin.tie(0), cout.tie(0);
    133 	int T = 1; cin >> T;
    134 	while(T--) solve();
    135 	return 0;
    136 }
    137 ```
    138 
    139 **Rate the problem**
    140 
    141 * Amazing:
    142 * Good:
    143 * OK:
    144 * Bad:
    145 * Terrible:
    146 
    147 [2277C - Edge Addeleting](/contest/2277/problem/C "Codeforces Round 1129 (Div. 2)")
    148 
    149 Author: [_O_v_O_](/profile/_O_v_O_ "Master _O_v_O_")
    150 
    151 **Hints**
    152 
    153 **Hint 1**
    154 
    155 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?
    156 
    157 **Hint 2**
    158 
    159 If you decide to keep the edge $(1, v_i)$, which original edge should you delete? When is keeping it useless?
    160 
    161 **Tutorial**
    162 
    163 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)$.
    164 
    165 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
    166 
    167 $ \max \left( \operatorname{dist}(1, n), \max_{\substack{1 \le i \le m \\ 1 \notin \operatorname{path}(v_i, n)}} (1 + \operatorname{dist}(v_i, n)) \right). $
    168 
    169 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.
    170 
    171 Time complexity per test case: $O(n + m)$.
    172 
    173 **Code**
    174 
    175 ```
    176 #include <bits/stdc++.h>
    177 
    178 using namespace std;
    179 
    180 constexpr int N = 500005;
    181 
    182 int n, m, d[N], ans;
    183 vector<int> to[N];
    184 queue<int> q;
    185 
    186 void solve() {
    187 	cin >> n >> m;
    188 	for(int u = 1; u <= n; ++u) {
    189 		d[u] = -1, to[u].clear();
    190 	}
    191 	for(int _ = 1; _ < n; ++_) {
    192 		int u, v; cin >> u >> v;
    193 		to[u].push_back(v);
    194 		to[v].push_back(u);
    195 	}
    196 	d[n] = 0, q.push(n);
    197 	while(q.size()) {
    198 		int u = q.front();
    199 		q.pop();
    200 		if(u == 1) continue;
    201 		for(int v : to[u]) {
    202 			if(d[v] < 0) {
    203 				d[v] = d[u] + 1;
    204 				q.push(v);
    205 			}
    206 		}
    207 	}
    208 	ans = d[1];
    209 	while(m--) {
    210 		int v; cin >> v;
    211 		ans = max(ans, d[v] + 1);
    212 	}
    213 	cout << ans << '\n';
    214 }
    215 
    216 int main() {
    217 	ios::sync_with_stdio(0);
    218 	cin.tie(0), cout.tie(0);
    219 	int T = 1; cin >> T;
    220 	while(T--) solve();
    221 	return 0;
    222 }
    223 ```
    224 
    225 **Rate the problem**
    226 
    227 * Amazing:
    228 * Good:
    229 * OK:
    230 * Bad:
    231 * Terrible:
    232 
    233 [2277D1 - Number Operating (Easy Version)](/contest/2277/problem/D1 "Codeforces Round 1129 (Div. 2)")
    234 
    235 Author: [Getaway_Car](/profile/Getaway_Car "Master Getaway_Car")
    236 
    237 **Hints**
    238 
    239 **Hint 1**
    240 
    241 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?
    242 
    243 **Hint 2**
    244 
    245 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)$.
    246 
    247 **Tutorial**
    248 
    249 Let $V = 10^{18}$. First, let us consider how to compute $f(n)$.
    250 
    251 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$.
    252 
    253 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:
    254 
    255 * 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$.
    256 * 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$.
    257 
    258 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$,
    259 
    260 $f(n) = \min\left(f(n - 2^k + 2) + k + 1,\ 2^{k + 1} - n + k\right).$
    261 
    262 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.
    263 
    264 Time complexity: $O(\sum (r - l + 1) \log V)$.
    265 
    266 **Code**
    267 
    268 ```
    269 #include <bits/stdc++.h>
    270 
    271 using namespace std;
    272 
    273 #define int long long
    274 
    275 constexpr int mod = 998'244'353;
    276 
    277 int l, r, ans;
    278 
    279 int f(int n) {
    280 	if(n <= 1) return n;
    281 	if(n == 2) return 3;
    282 	if(n == 3) return 2;
    283 	int k = __lg(n);
    284 	return min(f(n - (1ll << k) + 2) + k + 1, k + (1ll << (k + 1)) - n);
    285 }
    286 
    287 void solve() {
    288 	cin >> l >> r, ans = 0;
    289 	for(int i = l; i <= r; ++i) {
    290 		ans += f(i);
    291 	}
    292 	cout << ans % mod << '\n';
    293 	return;
    294 }
    295 
    296 signed main() {
    297 	ios::sync_with_stdio(0);
    298 	cin.tie(0), cout.tie(0);
    299 	int T = 1; cin >> T;
    300 	while(T--) solve();
    301 	return 0;
    302 }
    303 ```
    304 
    305 **Rate the problem**
    306 
    307 * Amazing:
    308 * Good:
    309 * OK:
    310 * Bad:
    311 * Terrible:
    312 
    313 [2277D2 - Number Operating (Hard Version)](/contest/2277/problem/D2 "Codeforces Round 1129 (Div. 2)")
    314 
    315 Author: [Getaway_Car](/profile/Getaway_Car "Master Getaway_Car")
    316 
    317 We'd like to thank [RockyYue](/profile/RockyYue "International Grandmaster RockyYue") for providing an optimized solution.
    318 
    319 **Hints**
    320 
    321 **Hint 1**
    322 
    323 Use the recursion from the easy version. How large can $f(n)$ be?
    324 
    325 **Hint 2**
    326 
    327 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})$.
    328 
    329 **Hint 3**
    330 
    331 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.
    332 
    333 **Tutorial**
    334 
    335 Let $g(n) = \sum \limits_{i = 0}^n f(i)$. Then the answer is $g(r) - g(l - 1)$.
    336 
    337 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})$.
    338 
    339 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
    340 
    341 $ \begin{aligned} g(n) &= g(2^k - 1) + \sum \limits_{i = 2^k}^w f(i) + \sum \limits_{i = w + 1}^n f(i)\\ &= g(2^k - 1) + \sum \limits_{i = 2^k}^w (f(i - 2^k + 2) + k + 1) + \sum \limits_{i = w + 1}^n f(i)\\ &= g(2^k - 1) + \sum \limits_{i = 2}^{w - 2^k + 2} (f(i) + k + 1) + \sum \limits_{i = w + 1}^n f(i)\\ &= g(2^k - 1) + g(w - 2^k + 2) - g(1) + (w - 2^k + 1)(k + 1) + \sum \limits_{i = w + 1}^n f(i). \end{aligned} $
    342 
    343 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.
    344 
    345 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$.
    346 
    347 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.
    348 
    349 Time complexity: $O(\log^4 V + t \log V)$.
    350 
    351 **Bonus**
    352 
    353 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.
    354 
    355 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
    356 
    357 $ g(n) = g(2^k - 1) + g(w - 2^k + 2) - g(1) + (w - 2^k + 1)(k + 1) + \frac{1}{2}(2^{k + 2} + 2k - w - n - 1)(n - w). $
    358 
    359 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)$.
    360 
    361 Time complexity: $O(\log^3 V + t \log V)$.
    362 
    363 **Computing $\mathrm{pos}_k$ in $O(\log V)$**
    364 
    365 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$.
    366 
    367 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.
    368 
    369 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.
    370 
    371 Time complexity: $O(\log^2 V + t \log V)$.
    372 
    373 **Code**
    374 
    375 ```
    376 #include <bits/stdc++.h>
    377 
    378 using namespace std;
    379 
    380 #define int long long
    381 
    382 constexpr int mod = 998'244'353;
    383 constexpr int inv2 = (mod + 1) >> 1;
    384 
    385 int l, r, pos[60], val[60];
    386 
    387 int g(int n) {
    388 	if(n <= 1) return max(n, 0ll);
    389 	int k = __lg(n), w = min(n, pos[k] + (1ll << k) - 2), res = 0;
    390 	res = val[k];
    391 	res = (res + g(w - (1ll << k) + 2) + mod - 1 + (w - (1ll << k) + 1) % mod * (k + 1)) % mod;
    392 	res = (res + ((1ll << (k + 2)) + 2 * k - w - n - 1) % mod * ((n - w) % mod) % mod * inv2) % mod;
    393 	return res;
    394 }
    395 
    396 void solve() {
    397 	cin >> l >> r;
    398 	cout << (g(r) + mod - g(l - 1)) % mod << '\n';
    399 	return;
    400 }
    401 
    402 signed main() {
    403 	ios::sync_with_stdio(0);
    404 	cin.tie(0), cout.tie(0);
    405 	for(int k = 0; k < 60; ++k) {
    406 		int lft = (1ll << k) + 1;
    407 		pos[k] = 1;
    408 		for(int i = k; i >= 2; --i)
    409 			if((1ll << i) + i - 1 <= lft)
    410 				lft -= (1ll << i) + i - 1, pos[k] += (1ll << i) - 2;
    411 		val[k] = g((1ll << k) - 1);
    412 	}
    413 	int T = 1; cin >> T;
    414 	while(T--) solve();
    415 	return 0;
    416 }
    417 ```
    418 
    419 **Rate the problem**
    420 
    421 * Amazing:
    422 * Good:
    423 * OK:
    424 * Bad:
    425 * Terrible:
    426 
    427 [2277E - Tree Guessing](/contest/2277/problem/E "Codeforces Round 1129 (Div. 2)")
    428 
    429 Author: [_O_v_O_](/profile/_O_v_O_ "Master _O_v_O_")
    430 
    431 **Hints**
    432 
    433 **Hint 1**
    434 
    435 Root the tree at vertex $1$. Can you find the size of every subtree with $n - 1$ queries?
    436 
    437 **Hint 2**
    438 
    439 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.
    440 
    441 **Hint 3**
    442 
    443 Give the vertices already placed in the tree values that increase with depth, and give the vertex being added the smallest value.
    444 
    445 **Tutorial**
    446 
    447 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.
    448 
    449 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}$.
    450 
    451 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.
    452 
    453 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$.
    454 
    455 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$.
    456 
    457 Time complexity per test case: $O(n^2)$.
    458 
    459 **Code**
    460 
    461 ```
    462 #include <bits/stdc++.h>
    463 
    464 using namespace std;
    465 
    466 constexpr int N = 505;
    467 
    468 int n, sz[N], p[N], a[N], cur, res, tmp;
    469 vector<int> to[N];
    470 queue<int> q;
    471 
    472 int query(int x, int *p) {
    473 	cout << "? " << x;
    474 	for(int u = 1; u <= n; ++u) {
    475 		cout << ' ' << p[u];
    476 	}
    477 	cout << endl;
    478 	int res; cin >> res;
    479 	return res;
    480 }
    481 
    482 void solve() {
    483 	cin >> n;
    484 	p[1] = n, p[2] = n - 1;
    485 	for(int u = 3; u <= n; ++u) {
    486 		p[u] = u - 2;
    487 	}
    488 	for(int u = 2; u <= n; ++u) {
    489 		swap(p[u - 1], p[u]);
    490 		sz[u] = query(1, p) - n * (n - 1);
    491 		a[u] = u;
    492 	}
    493 	a[1] = 1;
    494 	sort(a + 2, a + n + 1, [](int u, int v) {
    495 		return sz[u] > sz[v];
    496 	});
    497 	for(int i = 2; i <= n; ++i) {
    498 		cur = 1;
    499 		q.push(1);
    500 		while(q.size()) {
    501 			int u = q.front();
    502 			q.pop();
    503 			p[u] = ++cur;
    504 			for(int v : to[u]) {
    505 				q.push(v);
    506 			}
    507 		}
    508 		p[a[i]] = 1;
    509 		for(int j = i + 1; j <= n; ++j) {
    510 			p[a[j]] = j;
    511 		}
    512 		res = query(a[i], p);
    513 		res -= (i + 1 + n) * (n - i) / 2 + i;
    514 		for(int j = 1; j < i; ++j) {
    515 			tmp = p[a[j]] - 1;
    516 			if(res == tmp * (i - 1) + (i - tmp) * (i - tmp - 1) / 2) {
    517 				to[a[j]].push_back(a[i]);
    518 			}
    519 		}
    520 	}
    521 	cout << "!\n";
    522 	for(int u = 1; u <= n; ++u) {
    523 		for(int v : to[u]) {
    524 			cout << u << ' ' << v << '\n';
    525 		}
    526 		to[u].clear();
    527 	}
    528 	fflush(stdout);
    529 	return;
    530 }
    531 
    532 int main() {
    533 	int T = 1; cin >> T;
    534 	while(T--) solve();
    535 	return 0;
    536 }
    537 ```
    538 
    539 **Rate the problem**
    540 
    541 * Amazing:
    542 * Good:
    543 * OK:
    544 * Bad:
    545 * Terrible:
    546 
    547 [2277F - Token Re-Moving](/contest/2277/problem/F "Codeforces Round 1129 (Div. 2)")
    548 
    549 Author: [Getaway_Car](/profile/Getaway_Car "Master Getaway_Car")
    550 
    551 **Hints**
    552 
    553 **Hint 1**
    554 
    555 Fix the root $r$. When does the operation on $u$ have a non-zero cost, and what is the cost in that case?
    556 
    557 **Hint 2**
    558 
    559 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.
    560 
    561 **Hint 3**
    562 
    563 In that case, the cost depends only on the neighbor of $u$ in the direction of $r$, not on $r$ itself.
    564 
    565 **Tutorial**
    566 
    567 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$.
    568 
    569 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.
    570 
    571 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$.
    572 
    573 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$.
    574 
    575 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)$.
    576 
    577 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)$.
    578 
    579 Time complexity per test case: $O(n \log n)$ or $O(n \alpha(n))$.
    580 
    581 **Code**
    582 
    583 ```
    584 #include <bits/stdc++.h>
    585 
    586 using namespace std;
    587 
    588 constexpr int mod = 998'244'353;
    589 constexpr int N = 500005;
    590 
    591 void M(int &x) { x -= (x >= mod ? mod : 0); }
    592 
    593 int n, a[N], p[N], fa[N], ans[N], tmp;
    594 vector<int> to[N], nto[N];
    595 bool vis[N];
    596 
    597 struct DSU {
    598 	int fa[N];
    599 	void init(int n) {
    600 		for(int x = 1; x <= n; ++x) {
    601 			fa[x] = x;
    602 		}
    603 	}
    604 	int find(int x) {
    605 		return fa[x] == x ? x : fa[x] = find(fa[x]);
    606 	}
    607 	void merge(int x, int y) {
    608 		x = find(x), y = find(y);
    609 		if(x == y) return;
    610 		fa[x] = y;
    611 	}
    612 } dsu;
    613 
    614 void dfs1(int u) {
    615 	for(int v : to[u]) {
    616 		if(v != fa[u]) {
    617 			fa[v] = u, dfs1(v);
    618 			M(a[u] += a[v]);
    619 		}
    620 	}
    621 }
    622 
    623 void dfs2(int u) {
    624 	for(int v : nto[u]) {
    625 		M(ans[v] += ans[u]);
    626 		dfs2(v);
    627 	}
    628 }
    629 
    630 void solve() {
    631 	cin >> n;
    632 	for(int u = 1; u <= n; ++u) {
    633 		to[u].clear(), nto[u].clear(), ans[u] = 0;
    634 	}
    635 	for(int _ = 1; _ < n; ++_) {
    636 		int u, v; cin >> u >> v;
    637 		to[u].push_back(v);
    638 		to[v].push_back(u);
    639 	}
    640 	for(int u = 1; u <= n; ++u) {
    641 		cin >> a[u];
    642 	}
    643 	for(int i = 1; i <= n; ++i) {
    644 		cin >> p[i];
    645 	}
    646 	dfs1(1);
    647 	dsu.init(n);
    648 	for(int u = 1; u <= n; ++u) {
    649 		vis[u] = 0;
    650 	}
    651 	for(int i = n; i; --i) {
    652 		int &u = p[i];
    653 		for(int v : to[u]) {
    654 			if(vis[v]) {
    655 				if(v == fa[u]) {
    656 					v = dsu.find(v);
    657 					M(ans[v] += a[u]);
    658 				} else {
    659 					M(tmp = a[1] + mod - a[v]);
    660 					v = dsu.find(v);
    661 					M(ans[v] += tmp);
    662 				}
    663 				nto[u].push_back(v);
    664 				dsu.merge(v, u);
    665 			}
    666 		}
    667 		vis[u] = 1;
    668 	}
    669 	M(ans[p[1]] += a[1]), dfs2(p[1]);
    670 	for(int u = 1; u <= n; ++u) {
    671 		cout << ans[u] << " \n"[u == n];
    672 	}
    673 	return;
    674 }
    675 
    676 int main() {
    677 	ios::sync_with_stdio(0);
    678 	cin.tie(0), cout.tie(0);
    679 	int T = 1; cin >> T;
    680 	while(T--) solve();
    681 	return 0;
    682 }
    683 ```
    684 
    685 **Rate the problem**
    686 
    687 * Amazing:
    688 * Good:
    689 * OK:
    690 * Bad:
    691 * Terrible: