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: