codeforces-scrape

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

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 ```