1904.md (26048B)
1 Source: https://codeforces.com/blog/entry/123160 2 3 Sorry for the weak pretests on A :(. We hope you enjoyed the round nonetheless. 4 5 [1904A - Вилка!](/contest/1904/problem/A "Codeforces Round 914 (Div. 2)") 6 7 Idea: [Apple_Method](/profile/Apple_Method "Мастер Apple_Method") 8 Preparation: [Apple_Method](/profile/Apple_Method "Мастер Apple_Method")/[oursaco](/profile/oursaco "Международный мастер oursaco") 9 Analysis: [lunchbox](/profile/lunchbox "Мастер lunchbox") 10 11 **Solution** 12 13 There are at most $8$ positions of the knight that can attack a single cell. Therefore, we can find all $8$ positions that attack the king and the $8$ positions that attack the queen and count the number of positions that appear in both of these lists. 14 15 **Code** 16 17 ``` 18 #include <bits/stdc++.h> 19 using namespace std; 20 21 int dx[4] = {-1, 1, -1, 1}, dy[4] = {-1, -1, 1, 1}; 22 23 int main(){ 24 int t; cin >> t; 25 for(int i = 0; i < t; i++){ 26 int a, b; cin >> a >> b; 27 int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; 28 set<pair<int, int>> st1, st2; 29 for(int j = 0; j < 4; j++){ 30 st1.insert({x1+dx[j]*a, y1+dy[j]*b}); 31 st2.insert({x2+dx[j]*a, y2+dy[j]*b}); 32 st1.insert({x1+dx[j]*b, y1+dy[j]*a}); 33 st2.insert({x2+dx[j]*b, y2+dy[j]*a}); 34 } 35 int ans = 0; 36 for(auto x : st1) 37 if(st2.find(x) != st2.end()) 38 ans++; 39 cout << ans << '\n'; 40 } 41 } 42 ``` 43 44 [1904B - Игра в коллекционирование](/contest/1904/problem/B "Codeforces Round 914 (Div. 2)") 45 46 Idea: [oursaco](/profile/oursaco "Международный мастер oursaco") 47 Preparation: [oursaco](/profile/oursaco "Международный мастер oursaco") 48 Analysis: [lunchbox](/profile/lunchbox "Мастер lunchbox") 49 50 **Solution** 51 52 Let's sort array $a$. The answer for the largest element is $n-1$ because the score, which is $a_n$, cannot be smaller than any of the other elements. Now, consider the second largest element. The answer is at least $n-2$ because every element that is not greater than $a_{n-1}$ can be taken. Then, we check if the score is at least $a_n$. This inspires the following solution: first, we find the prefix sum $p$ of array $a$. We calculate the answer in decreasing order of $a_i$. To calculate the answer for an $a_i$, we find the largest $j$ such that $p_i\geq a_j$ and set the answer for $i$ equal to the answer of $j$. 53 54 **Code** 55 56 ``` 57 #include <bits/stdc++.h> 58 #include <ext/pb_ds/assoc_container.hpp> 59 #include <ext/pb_ds/tree_policy.hpp> 60 using namespace __gnu_pbds; 61 using namespace std; 62 63 #define pb push_back 64 #define ff first 65 #define ss second 66 67 typedef long long ll; 68 typedef long double ld; 69 typedef pair<int, int> pii; 70 typedef pair<ll, ll> pll; 71 typedef pair<ld, ld> pld; 72 73 const int INF = 1e9; 74 const ll LLINF = 1e18; 75 const int MOD = 1e9 + 7; 76 77 template<class K> using sset = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>; 78 79 inline ll ceil0(ll a, ll b) { 80 return a / b + ((a ^ b) > 0 && a % b); 81 } 82 83 void setIO() { 84 ios_base::sync_with_stdio(0); cin.tie(0); 85 } 86 87 int main(){ 88 setIO(); 89 int T; 90 cin >> T; 91 for(int tt = 1; tt <= T; tt++){ 92 int n; 93 cin >> n; 94 pii arr[n + 1]; 95 for(int i = 1; i <= n; i++) cin >> arr[i].ff, arr[i].ss = i; 96 sort(arr + 1, arr + n + 1); 97 int nxt[n + 1]; 98 ll sum[n + 1]; 99 int ans[n + 1]; 100 nxt[0] = sum[0] = 0; 101 for(int i = 1; i <= n; i++){ 102 if(nxt[i - 1] >= i){ 103 nxt[i] = nxt[i - 1]; 104 sum[i] = sum[i - 1]; 105 } else { 106 sum[i] = sum[i - 1] + arr[i].ff; 107 nxt[i] = i; 108 while(nxt[i] + 1 <= n && sum[i] >= arr[nxt[i] + 1].ff){ 109 nxt[i]++; 110 sum[i] += arr[nxt[i]].ff; 111 } 112 } 113 ans[arr[i].ss] = nxt[i]; 114 } 115 for(int i = 1; i <= n; i++) cout << ans[i] - 1 << " "; 116 cout << endl; 117 } 118 } 119 ``` 120 121 [1904C - Игра с массивом](/contest/1904/problem/C "Codeforces Round 914 (Div. 2)") 122 123 Idea: [lunchbox](/profile/lunchbox "Мастер lunchbox") 124 Preparation: [lunchbox](/profile/lunchbox "Мастер lunchbox") 125 Analysis: [lunchbox](/profile/lunchbox "Мастер lunchbox") 126 127 **Solution** 128 129 If $k\geq 3$, the answer is equal to $0$ since after performing an operation on the same pair $(i, j)$ twice, performing an operation on the two new values (which are the same) results in $0$. 130 131 Therefore, let's consider the case for $1\leq k\leq 2$. 132 133 For $k=1$, it is sufficient to sort the array and output the minimum between $a_i$ and $a_{i+1} - a_i$. 134 135 For $k=2$, let's brute force the first operation. If the newly created value is $v$, then it is sufficient to find the smallest $a_i$ satisfying $a_i\geq v$ and greatest $a_i$ satisfying $a_i\leq v$ and relax the answer on $|a_i - v|$. Also, remember to consider the cases of performing no operation or one operation. This runs in $O(N^2\log N)$. There also exists a solution in $O(N^2)$ using a two pointers approach. 136 137 **Code** 138 139 ``` 140 #include <bits/stdc++.h> 141 using namespace std; 142 143 #define int long long 144 145 signed main() { 146 int t; 147 cin >> t; 148 while (t--) { 149 int n, k; 150 cin >> n >> k; 151 vector<int> a(n); 152 for (int i = 0; i < n; i++) cin >> a[i]; 153 if (k >= 3) { 154 cout << 0 << endl; 155 continue; 156 } 157 sort(begin(a), end(a)); 158 int d = a[0]; 159 for (int i = 0; i < n - 1; i++) d = min(d, a[i + 1] - a[i]); 160 if (k == 1) { 161 cout << d << endl; 162 continue; 163 } 164 for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) { 165 int v = a[i] - a[j]; 166 int p = lower_bound(begin(a), end(a), v) - begin(a); 167 if (p < n) d = min(d, a[p] - v); 168 if (p > 0) d = min(d, v - a[p - 1]); 169 } 170 cout << d << endl; 171 } 172 } 173 ``` 174 175 [1904D1 - Присвоить максимум (простая версия)](/contest/1904/problem/D1 "Codeforces Round 914 (Div. 2)") / [1904D2 - Присвоить максимум (сложная версия)](/contest/1904/problem/D2 "Codeforces Round 914 (Div. 2)") 176 177 Idea: [oursaco](/profile/oursaco "Международный мастер oursaco") 178 Preparation: [oursaco](/profile/oursaco "Международный мастер oursaco") 179 Analysis: [oursaco](/profile/oursaco "Международный мастер oursaco") 180 181 **Hint 1** 182 183 Can we reduce the number of intervals we want to apply an operation on? 184 185 **Hint 2** 186 187 What is the necessary condition to perform an operation on an interval 188 189 **Solution** 190 191 If $b_i \lt a_i$ for any $i$, then it is clearly impossible. 192 193 In order for $a_i$ to become $b_i$, $i$ must be contained by an interval that also contains a $j$ where $a_j = b_i$. Note that if there is a triple $i \le j \lt k$ where $a_j = a_k = b_i$, then it is never optimal to apply the operation on interval $[i, k]$, since applying the operation on interval $[i, j]$ will be sufficient. Thus, for $i$ we only need to consider the closest $a_j = b_i$ to the right or left of $i$. 194 195 Lets find the necessary conditions for us to apply an operation on the interval $[i, j]$. First of all, $a_k \le b_i$ for $i \le k \le j$. Second, $b_k \ge b_i$ for all $i \le k \le j$. Turns out, these conditions are also sufficient, since we can apply these operations in increasing order of $b_i$ without them interfering with each other. If we check for every $i$ there exists an interval $[i, j]$ or $[j, i]$ that satisfies the necessary conditions, then there will exist a sequence of operations to transform $a$ into $b$. Checking for the conditions can be done with brute force for D1 or using monotonic stacks or segment trees for D2. 196 197 **Code** 198 199 ``` 200 #include <bits/stdc++.h> 201 #include <ext/pb_ds/assoc_container.hpp> 202 #include <ext/pb_ds/tree_policy.hpp> 203 using namespace __gnu_pbds; 204 using namespace std; 205 206 #define pb push_back 207 #define ff first 208 #define ss second 209 210 typedef long long ll; 211 typedef long double ld; 212 typedef pair<int, int> pii; 213 typedef pair<ll, ll> pll; 214 typedef pair<ld, ld> pld; 215 216 const int INF = 1e9; 217 const ll LLINF = 1e18; 218 const int MOD = 1e9 + 7; 219 220 template<class K> using sset = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>; 221 222 inline ll ceil0(ll a, ll b) { 223 return a / b + ((a ^ b) > 0 && a % b); 224 } 225 226 void setIO() { 227 ios_base::sync_with_stdio(0); cin.tie(0); 228 } 229 230 int main(){ 231 setIO(); 232 int T; 233 cin >> T; 234 for(int tt = 1; tt <= T; tt++){ 235 int n; 236 cin >> n; 237 int a[n + 1], b[n + 1]; 238 for(int i = 1; i <= n; i++) cin >> a[i]; 239 for(int i = 1; i <= n; i++) cin >> b[i]; 240 bool val[n + 1]; 241 memset(val, false, sizeof(val)); 242 for(int t = 0; t < 2; t++){ 243 int prvb[n + 1]; //prev smaller 244 int nxta[n + 1]; //next greater 245 stack<pii> s; 246 s.push({INF, n + 1}); 247 for(int i = n; i >= 1; i--){ 248 while(s.top().ff <= a[i]) s.pop(); 249 nxta[i] = s.top().ss; 250 s.push({a[i], i}); 251 } 252 while(!s.empty()) s.pop(); 253 s.push({0, 0}); 254 for(int i = 1; i <= n; i++){ 255 while(s.top().ff >= b[i]) s.pop(); 256 prvb[i] = s.top().ss; 257 s.push({b[i], i}); 258 } 259 int m[n + 1]; 260 memset(m, 0, sizeof(m)); 261 for(int i = 1; i <= n; i++){ 262 m[a[i]] = i; 263 if(a[i] <= b[i] && m[b[i]]) val[i] |= prvb[i] < m[b[i]] && nxta[m[b[i]]] > i; 264 } 265 reverse(a + 1, a + n + 1); 266 reverse(b + 1, b + n + 1); 267 reverse(val + 1, val + n + 1); 268 } 269 bool ans = true; 270 for(int i = 1; i <= n; i++) ans &= val[i]; 271 cout << (ans ? "YES" : "NO") << endl; 272 } 273 } 274 ``` 275 276 [1904E - Запросы на дереве](/contest/1904/problem/E "Codeforces Round 914 (Div. 2)") 277 278 Idea: [Apple_Method](/profile/Apple_Method "Мастер Apple_Method") 279 Preparation: [oursaco](/profile/oursaco "Международный мастер oursaco") 280 281 Editorial 1: 282 Analysis: [oursaco](/profile/oursaco "Международный мастер oursaco") 283 284 Thanks to [errorgorn](/profile/errorgorn "Международный гроссмейстер errorgorn") for the solution! 285 286 **Hint 1** 287 288 The solution doesn't involve virtual tree 289 290 **Hint 2** 291 292 What is an easy way to represent the tree? 293 294 **Solution** 295 296 Consider the Euler tour of the tree where $in[u]$ is the entry time of each node and $out[u]$ is the exit time. The interval $[in[u], out[u]]$ corresponds to the subtree of $u$. 297 298 Removing a node is equivalent to blocking some intervals on the Euler tour. There are two cases when $a$ is blocked with respect to query node $x$. If $a$ is an ancestor of $x$, then the set of reachable nodes is reduced to the interval $[in[nxt_a], out[nxt_a]]$, where $nxt_a$ is the first node on the path from $a$ to $x$. This is equivalent to blocking the intervals $[0, in[nxt_a])$ and $(out[nxt_a], n - 1]$. If $a$ is not an ancestor, then the interval $[in[a], out[a]]$ is blocked. 299 300 Lets build a lazy segment tree on the Euler tour of the tree. Each leaf node will correspond to the depth of a node on the tree. We can re-root the tree from $a$ to $b$ by subtracting one from all nodes the range $[in[b], out[b]]$ and adding one to all other nodes. Thus, we can traverse the tree while re-rooting and process our queries offline. When the query node $x$ is the root, block all the necessary intervals and then find the maximum value in the segment tree. 301 302 **Code** 303 304 ``` 305 #include <bits/stdc++.h> 306 #include <ext/pb_ds/assoc_container.hpp> 307 #include <ext/pb_ds/tree_policy.hpp> 308 using namespace __gnu_pbds; 309 using namespace std; 310 311 #define pb push_back 312 #define ff first 313 #define ss second 314 315 typedef long long ll; 316 typedef long double ld; 317 typedef pair<int, int> pii; 318 typedef pair<ll, ll> pll; 319 typedef pair<ld, ld> pld; 320 321 const int INF = 1e9; 322 const ll LLINF = 1e18; 323 const int MOD = 1e9 + 7; 324 325 template<class K> using sset = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>; 326 327 inline ll ceil0(ll a, ll b) { 328 return a / b + ((a ^ b) > 0 && a % b); 329 } 330 331 void setIO() { 332 ios_base::sync_with_stdio(0); cin.tie(0); 333 } 334 335 const int MAXN = 2e5; 336 const int MAXQ = 2e5; 337 338 int seg[4*MAXN + 5]; 339 int tag[4*MAXN + 5]; 340 int tim; 341 vector<int> g[MAXN + 5]; 342 int in[MAXN + 5], out[MAXN + 5]; 343 344 void push_down(int cur){ 345 if(!tag[cur]) return; 346 for(int i = cur*2 + 1; i <= cur*2 + 2; i++){ 347 seg[i] += tag[cur]; 348 tag[i] += tag[cur]; 349 } 350 tag[cur] = 0; 351 } 352 353 void update(int l, int r, int v, int ul = 0, int ur = tim - 1, int cur = 0){ 354 if(l <= ul && ur <= r){ 355 seg[cur] += v; 356 tag[cur] += v; 357 return; 358 } 359 push_down(cur); 360 int mid = (ul + ur)/2; 361 if(l <= mid) update(l, r, v, ul, mid, cur*2 + 1); 362 if(r > mid) update(l, r, v, mid + 1, ur, cur*2 + 2); 363 seg[cur] = max(seg[cur*2 + 1], seg[cur*2 + 2]); 364 } 365 366 int query(int l, int r, int ul = 0, int ur = tim - 1, int cur = 0){ 367 if(l <= ul && ur <= r) return seg[cur]; 368 push_down(cur); 369 int mid = (ul + ur)/2; 370 if(r <= mid) return query(l, r, ul, mid, cur*2 + 1); 371 if(l > mid) return query(l, r, mid + 1, ur, cur*2 + 2); 372 return max(query(l, r, ul, mid, cur*2 + 1), query(l, r, mid + 1, ur, cur*2 + 2)); 373 } 374 375 void dfs1(int x, int p = 0){ 376 in[x] = tim++; 377 for(int i : g[x]){ 378 if(i == p) continue; 379 dfs1(i, x); 380 } 381 out[x] = tim - 1; 382 } 383 384 vector<pair<int, vector<int>>> que[MAXN + 5]; 385 int nxt[MAXN + 5]; 386 int ans[MAXQ + 5]; 387 int n, q; 388 389 void dfs2(int x, int p = 0){ 390 for(auto &i : que[x]){ 391 vector<pii> skip; 392 bool found = false; 393 for(int j : i.ss){ 394 if(j == x){ 395 found = true; 396 break; 397 } 398 if(in[j] <= in[x] && in[x] <= out[j]){ 399 skip.pb({0, in[nxt[j]] - 1}); 400 skip.pb({out[nxt[j]] + 1, tim - 1}); 401 } else { 402 skip.pb({in[j], out[j]}); 403 } 404 } 405 if(found) continue; 406 sort(skip.begin(), skip.end()); 407 int prv = 0; 408 for(pii j : skip){ 409 if(prv < j.ff) ans[i.ff] = max(ans[i.ff], query(prv, j.ff - 1)); 410 prv = max(prv, j.ss + 1); 411 } 412 if(prv <= tim - 1) ans[i.ff] = max(ans[i.ff], query(prv, tim - 1)); 413 } 414 update(0, tim - 1, 1); 415 for(int i : g[x]){ 416 if(i == p) continue; 417 update(in[i], out[i], -2); 418 nxt[x] = i; 419 dfs2(i, x); 420 update(in[i], out[i], 2); 421 } 422 update(0, tim - 1, -1); 423 } 424 425 int main(){ 426 setIO(); 427 cin >> n >> q; 428 for(int i = 0; i < n - 1; i++){ 429 int a, b; 430 cin >> a >> b; 431 g[a].pb(b); 432 g[b].pb(a); 433 } 434 tim = 0; 435 dfs1(1); 436 for(int i = 0; i < q; i++){ 437 int x, k; 438 cin >> x >> k; 439 vector<int> v(k); 440 for(int j = 0; j < k; j++) cin >> v[j]; 441 que[x].pb({i, v}); 442 } 443 for(int i = 2; i <= n; i++) update(in[i], out[i], 1); 444 dfs2(1); 445 for(int i = 0; i < q; i++){ 446 cout << ans[i] << endl; 447 } 448 } 449 ``` 450 451 Editorial 2: 452 Analysis: [willy108](/profile/willy108 "Мастер willy108") 453 454 **Hint 1** 455 456 In a tree, one of the farthest nodes from some node $x$ is one of the two endpoints of the diameter. 457 458 **Hint 2** 459 460 Let's try to find the diameter of the connected subgraph node $x$ is in after the nodes $a_{1 \dots n}$ are removed. 461 462 **Hint 3** 463 464 Consider an euler tour of the tree and order the nodes by their inorder traversal. When $k$ nodes are removed, the remaining nodes form $O(k)$ contiguous intervals in the tour. 465 466 **Solution** 467 468 Let's build a segtree/sparse table where each node stores the diameter (as a pair of nodes) for the nodes with $in$ values in the range $[l, r]$. To merge two diameters, we can enumerate all $4 \choose 2$ ways to pick the new diameter and take the best one. 469 470 To answer a query, we can first generate a list of banned intervals (just like solution 1) and use that list to generate the list of unbanned intervals. Then we can query our segtree for the diameter of each of ranges. Finally, we can combine the answers of the seperate queries to obtain the diameter of the connected subgraph. We know the farthest node from node $x$ is one of the two endpoints, so it suffices to just manually check the distance of those two nodes. 471 472 Final complexity is $O(n \log^2 n + \sum k \log n)$. 473 474 **Code** 475 476 ``` 477 #include <bits/stdc++.h> 478 479 #define sz(x) ((int)(x.size())) 480 #define all(x) x.begin(), x.end() 481 #define pb push_back 482 #define eb emplace_back 483 484 const int MX = 2e5 +10, int_max = 0x3f3f3f3f; 485 486 using namespace std; 487 488 //lca template start 489 vector<int> dep, sz, par, head, tin, tout, tour; 490 vector<vector<int>> adj; 491 int n, ind, q; 492 void dfs(int x, int p){ 493 sz[x] = 1; 494 dep[x] = dep[p] + 1; 495 par[x] = p; 496 for(auto &i : adj[x]){ 497 if(i == p) continue; 498 dfs(i, x); 499 sz[x] += sz[i]; 500 if(adj[x][0] == p || sz[i] > sz[adj[x][0]]) swap(adj[x][0], i); 501 } 502 if(p != 0) adj[x].erase(find(all(adj[x]), p)); 503 } 504 void dfs2(int x, int p){ 505 tour[ind] = x; 506 tin[x] = ind++; 507 for(auto &i : adj[x]){ 508 if(i == p) continue; 509 head[i] = (i == adj[x][0] ? head[x] : i); 510 dfs2(i, x); 511 } 512 tout[x] = ind; 513 } 514 515 int k_up(int u, int k){ 516 if(dep[u] <= k) return -1; 517 while(k > dep[u] - dep[head[u]]){ 518 k -= dep[u] - dep[head[u]] + 1; 519 u = par[head[u]]; 520 } 521 return tour[tin[u] - k]; 522 } 523 524 int lca(int a, int b){ 525 while(head[a] != head[b]){ 526 if(dep[head[a]] > dep[head[b]]) swap(a, b); 527 b = par[head[b]]; 528 } 529 if(dep[a] > dep[b]) swap(a, b); 530 return a; 531 } 532 533 int dist(int a, int b){ 534 return dep[a] + dep[b] - 2*dep[lca(a, b)]; 535 } 536 //lca template end 537 //segtree template start 538 #define ff first 539 #define ss second 540 int dist(pair<int, int> a){ 541 return dist(a.ff, a.ss); 542 } 543 pair<int, int> merge(pair<int, int> a, pair<int, int> b){ 544 auto p = max(pair(dist(a), a), pair(dist(b), b)); 545 for(auto x : {a.ff, a.ss}){ 546 for(auto y : {b.ff, b.ss}){ 547 if(x == 0 || y == 0) continue; 548 p = max(p, pair(dist(pair(x, y)), pair(x, y))); 549 } 550 } 551 return p.ss; 552 } 553 554 pair<int, int> mx[MX*4]; 555 #define LC(k) (2*k) 556 #define RC(k) (2*k +1) 557 void update(int p, int v, int k, int L, int R){ 558 if(L + 1 == R){ 559 mx[k] = {tour[p], tour[p]}; 560 return ; 561 } 562 int mid = (L + R)/2; 563 if(p < mid) update(p, v, LC(k), L, mid); 564 else update(p, v, RC(k), mid, R); 565 mx[k] = merge(mx[LC(k)], mx[RC(k)]); 566 } 567 568 void query(int qL, int qR, vector<pair<int, int>>& ret, int k, int L, int R){ 569 if(qR <= L || R <= qL) return ; 570 if(qL <= L && R <= qR){ 571 ret.push_back(mx[k]); 572 return ; 573 } 574 int mid = (L + R)/2; 575 query(qL, qR, ret, LC(k), L, mid); 576 query(qL, qR, ret, RC(k), mid, R); 577 } 578 579 //segtree template end 580 581 int query(vector<int> arr, int x){ 582 vector<pair<int, int>> banned, ret; 583 for(int u : arr){ 584 if(lca(u, x) == u){ 585 u = k_up(x, dep[x] - dep[u] - 1); 586 banned.push_back({0, tin[u]}); 587 banned.push_back({tout[u], n}); 588 }else{ 589 banned.push_back({tin[u], tout[u]}); 590 } 591 } 592 sort(all(banned), [&](pair<int, int> a, pair<int, int> b){ 593 return (a.ff < b.ff) || (a.ff == b.ff && a.ss > b.ss); 594 }); 595 vector<pair<int, int>> tbanned; //remove nested intervals 596 int mx = 0; 597 for(auto [a, b] : banned){ 598 if(b <= mx) continue; 599 else if(a != b){ 600 tbanned.pb({a, b}); 601 mx = b; 602 } 603 } 604 605 banned = tbanned; 606 int tim = 0; 607 for(auto [a, b] : banned){ 608 if(tim < a) 609 query(tim, a, ret, 1, 0, n); 610 tim = b; 611 } 612 613 if(tim < n) 614 query(tim, n, ret, 1, 0, n); 615 pair<int, int> dia = pair(x, x); 616 for(auto p : ret) dia = merge(dia, p); 617 int ans = max(dist(x, dia.ff), dist(x, dia.ss)); 618 return ans; 619 } 620 621 void solve(){ 622 cin >> n >> q; 623 dep = sz = par = head = tin = tout = tour = vector<int>(n+1, 0); 624 adj = vector<vector<int>>(n+1); 625 for(int i = 1; i<n; i++){ 626 int a, b; 627 cin >> a >> b; 628 adj[a].push_back(b); 629 adj[b].push_back(a); 630 } 631 632 dfs(1, 0); 633 head[1] = 1; 634 dfs2(1, 0); 635 for(int i = 1; i<=n; i++){ 636 update(tin[i], dep[i], 1, 0, n); 637 } 638 for(int i = 1; i<=q; i++){ 639 int x, k; 640 cin >> x >> k; 641 vector<int> arr(k); 642 for(int& y : arr) cin >> y; 643 cout << query(arr, x) << "\n"; 644 } 645 } 646 647 signed main(){ 648 cin.tie(0) -> sync_with_stdio(0); 649 650 int T = 1; 651 //cin >> T; 652 for(int i = 1; i<=T; i++){ 653 //cout << "Case #" << i << ": "; 654 solve(); 655 } 656 return 0; 657 } 658 ``` 659 660 [1904F - Прекрасное дерево](/contest/1904/problem/F "Codeforces Round 914 (Div. 2)") 661 662 Idea: [Apple_Method](/profile/Apple_Method "Мастер Apple_Method") 663 Preparation: [oursaco](/profile/oursaco "Международный мастер oursaco") 664 Analysis: [Apple_Method](/profile/Apple_Method "Мастер Apple_Method") 665 666 **Hint** 667 668 Can we represent the conditions as a graph? 669 670 **Solution** 671 672 Lets rewrite the condition that node $a$ must be smaller than node $b$ as a directed edge from $a$ to $b$. Then, we can assign each node a value based on the topological sort of this new directed graph. If this directed graph had a cycle, it is clear that there is no way to order the nodes. 673 674 With this in mind, we can try to construct a graph that would have these properties. Once we have the graph, we can topological sort to find the answer. 675 676 For now, let's consider the problem if it only had type 1 requirements (type 2 requirements can be done very similarly). 677 678 Thus, the problem reduces to "given a path and a node, add a directed edge from the node to every node in that path." To do this, we can use binary lifting. For each node, create $k$ dummy nodes, the $i$th of which represents the minimum number from the path between node $a$ and the $2^i$th parent of $a$. Now, we can draw a directed edge from the the $i$th dummy node of $a$ to the $i-1$th dummy node of $a$ and the $i-1$th dummy node of the $2^{i-1}$th parent of $a$. 679 680 Now, to add an edge from any node to a vertical path of the tree, we can repeatedly add an edge from that node to the largest node we can. This will add $O(\log n)$ edges per requirement. 681 682 The final complexity is $O((n+m)\log n)$ time and $O((n+m)\log n)$. 683 684 **Code** 685 686 ``` 687 #pragma GCC optimize("O3,unroll-loops") 688 #pragma GCC target("avx,avx2,fma") 689 #pragma GCC target("sse4,popcnt,abm,mmx,tune=native") 690 #include <bits/stdc++.h> 691 #include <ext/pb_ds/assoc_container.hpp> 692 #include <ext/pb_ds/tree_policy.hpp> 693 using namespace __gnu_pbds; 694 using namespace std; 695 696 #define pb push_back 697 #define ff first 698 #define ss second 699 700 typedef long long ll; 701 typedef long double ld; 702 typedef pair<int, int> pii; 703 typedef pair<ll, ll> pll; 704 typedef pair<ld, ld> pld; 705 706 const int INF = 1e9; 707 const ll LLINF = 1e18; 708 const int MOD = 1e9 + 7; 709 710 template<class K> using sset = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>; 711 712 inline ll ceil0(ll a, ll b) { 713 return a / b + ((a ^ b) > 0 && a % b); 714 } 715 716 void setIO() { 717 ios_base::sync_with_stdio(0); cin.tie(0); 718 } 719 720 const int MAXN = 200'000; 721 const int LG = 18; 722 const int MAXM = 200'000; 723 724 vector<int> g[MAXN + 5]; 725 int sz[MAXN + 5], in[MAXN + 5], par[MAXN + 5], depth[MAXN + 5], head[MAXN + 5], tim; 726 int n, m; 727 728 void dfs1(int x, int p){ 729 sz[x] = 1; 730 for(int &i : g[x]){ 731 if(i == p) continue; 732 dfs1(i, x); 733 sz[x] += sz[i]; 734 if(g[x][0] == p || sz[i] > sz[g[x][0]]) swap(g[x][0], i); 735 } 736 } 737 738 void dfs2(int x, int p){ 739 in[x] = tim++; 740 par[x] = p; 741 depth[x] = depth[p] + 1; 742 for(int i : g[x]){ 743 if(i == p) continue; 744 head[i] = (i == g[x][0] ? head[x] : i); 745 dfs2(i, x); 746 } 747 } 748 749 const int MAXSZ = MAXN + 2*MAXN*LG; 750 int down[LG][MAXN + 5]; 751 int up[LG][MAXN + 5]; 752 vector<int> dag[MAXSZ+ 5]; 753 int lg[MAXN + 5]; 754 755 void upd(int l, int r, int x, int t){ 756 if(l <= in[x] && in[x] <= r){ 757 if(l < in[x]) upd(l, in[x] - 1, x, t); 758 if(in[x] < r) upd(in[x] + 1, r, x, t); 759 } else { 760 int sz = lg[r - l + 1]; 761 if(t == 2){ 762 dag[up[sz][l]].pb(x); 763 dag[up[sz][r - (1 << sz) + 1]].pb(x); 764 } else { 765 dag[x].pb(down[sz][l]); 766 dag[x].pb(down[sz][r - (1 << sz) + 1]); 767 } 768 } 769 } 770 771 //1 is down, 2 is up 772 void draw(int a, int b, int c, int t){ 773 while(head[a] != head[b]){ 774 if(depth[head[a]] > depth[head[b]]) swap(a, b); 775 upd(in[head[b]], in[b], c, t); 776 b = par[head[b]]; 777 } 778 if(depth[a] > depth[b]) swap(a, b); 779 upd(in[a], in[b], c, t); 780 } 781 782 bool vis[MAXSZ + 5], stk[MAXSZ + 5]; 783 vector<int> ord; 784 bool fail; 785 int ind; 786 787 void dfs3(int x){ 788 if(fail) return; 789 vis[x] = stk[x] = true; 790 for(int i : dag[x]){ 791 if(i == x) continue; 792 if(!vis[i]){ 793 dfs3(i); 794 } else if(stk[i]){ 795 fail = true; 796 break; 797 } 798 } 799 stk[x] = false; 800 if(x <= n) ord.pb(x); 801 } 802 803 int main(){ 804 setIO(); 805 cin >> n >> m; 806 lg[1] = 0; 807 for(int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1; 808 for(int i = 0; i < n - 1; i++){ 809 int a, b; 810 cin >> a >> b; 811 g[a].pb(b); 812 g[b].pb(a); 813 } 814 tim = 0; 815 dfs1(1, 1); 816 head[1] = 1; 817 dfs2(1, 1); 818 for(int i = 1; i <= n; i++) down[0][in[i]] = up[0][in[i]] = i; 819 ind = n + 1; 820 for(int i = 1; i < LG; i++){ 821 for(int j = 0; j + (1 << i) <= n; j++){ 822 down[i][j] = ind++; 823 up[i][j] = ind++; 824 825 dag[down[i][j]].pb(down[i - 1][j]); 826 dag[down[i][j]].pb(down[i - 1][j + (1 << (i - 1))]); 827 828 dag[up[i - 1][j]].pb(up[i][j]); 829 dag[up[i - 1][j + (1 << (i - 1))]].pb(up[i][j]); 830 } 831 } 832 for(int i = 0; i < m; i++){ 833 int t, a, b, c; 834 cin >> t >> a >> b >> c; 835 draw(a, b, c, t); 836 } 837 fail = false; 838 for(int i = 1; i <= n; i++){ 839 if(!vis[i]){ 840 dfs3(i); 841 if(fail) break; 842 } 843 } 844 if(fail){ 845 cout << -1 << endl; 846 return 0; 847 } 848 reverse(ord.begin(), ord.end()); 849 int ans[n + 1]; 850 for(int i = 0; i < ord.size(); i++){ 851 ans[ord[i]] = i + 1; 852 } 853 for(int i = 1; i <= n; i++) cout << ans[i] << " "; 854 cout << endl; 855 } 856 ```