codeforces-scrape

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

1208.md (24527B)


      1 Source: https://codeforces.com/blog/entry/69357
      2 
      3 ### [1208A — XORinacci](https://codeforces.com/contest/1208/problem/A)
      4 
      5 The sequence is $a$, $b$, $a\oplus b$, $a$, $b$, $a\oplus b$ $\cdots$
      6 
      7 Since, the sequence has a period of $3$, $f[i] = f[i \mod 3]$.
      8 
      9 **Code**
     10 
     11 ```
     12 #include<bits/stdc++.h>
     13 using namespace std;
     14 int main()
     15 {
     16     int test,a,b,n;
     17     cin>>test;
     18     while(test--){
     19         cin>>a>>b>>n;
     20         switch (n%3){
     21             case 0:
     22               cout<<a<<endl;
     23               break;
     24             case 1:
     25               cout<<b<<endl;
     26               break;
     27             default:
     28               cout<<(a^b)<<endl;
     29         }
     30     }
     31     return 0;
     32 }
     33 ```
     34 
     35 ### [1208B — Uniqueness](https://codeforces.com/contest/1208/problem/B)
     36 
     37 After removing a sub-segment, a prefix and a suffix remain, possibly of length $0$. Let us fix the prefix which does not contain any duplicate elements and find the maximum suffix we can get without repeating the elements. We can use map/set to keep track of the elements.
     38 
     39 Time complexity: $O(n^2 \cdot log(n))$
     40 
     41 **Code**
     42 
     43 ```
     44 #include <bits/stdc++.h>
     45 
     46 using namespace std;
     47 
     48 const int N = 2e3 + 5;
     49 int a[N];
     50 
     51 int main(){
     52     int n;
     53     scanf("%d", &n);
     54     for(int i = 0; i < n; ++i){
     55         scanf("%d", &a[i]);
     56     }
     57 
     58     int ans = n - 1;
     59     map<int, int> freq; 
     60     for(int i = 0; i < n; ++i){
     61         bool validPrefix = true;
     62         for(int j = 0; j < i; ++j){
     63             freq[a[j]]++;
     64             if(freq[a[j]] == 2){
     65                 validPrefix = false;
     66                 break;
     67             }
     68         }
     69         int min_index_suffix = n;
     70         for(int j = n - 1; j >= i; --j){
     71             freq[a[j]]++;
     72             if(freq[a[j]] == 1){
     73                 min_index_suffix = j;
     74             }
     75             else break;
     76         }
     77         if(validPrefix){
     78             ans = min(ans, min_index_suffix - i);
     79         }
     80         
     81         freq.clear();
     82     }
     83     cout << ans << '\n';
     84 ```
     85 
     86 **Bonus**
     87 
     88 Try to solve this problen in $O(n \cdot log(n))$
     89 
     90 ### [1208C — Magic Grid](https://codeforces.com/contest/1208/problem/C)
     91 
     92 Divide the grid into four quadrants. Assign distinct integers to the first quadrant from $0$ to $(\frac{N^2}{4} - 1)$. Copy this quadrant to the other three. This way XOR of each row and column becomes $0$.
     93 
     94 Now, to make numbers distinct among the quadrants, multiply the numbers by $4$. Add $1$, $2$, and $3$ to the numbers in $1^{st}$, $2^{nd}$ and $3^{rd}$ quadrants respectively. The XOR of each row and column would still remain $0$ as $N/2$ is also even but the elements will become distinct while being in the range $[0, N^2-1].$
     95 
     96 Another approach in this problem is to use a $ 4 \times 4$ grid given in the sample itself and replicate it in $N \times N$ grid by adding $16, 32, 48 \cdots $ to make the elements distinct.
     97 
     98 Of course, there are multiple ways to solve the problem. These are just a few of them.
     99 
    100 **Code**
    101 
    102 ```
    103 #include <bits/stdc++.h>
    104 using namespace std;
    105 #define int     long long
    106 #define ld      long double
    107 #define pii     pair<int ,int>
    108 #define pld     pair<ld ,ld>
    109 #define F       first
    110 #define S       second
    111 #define mod     1000000007
    112 #define pb      push_back
    113 #define mp      make_pair
    114 #define all(x)  x.begin(),x.end()
    115 #define mset(x) memset(x, 0, sizeof(x));
    116 #define ios     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    117 
    118 const int N = 1000;
    119 
    120 int n, grid[N][N];
    121 void run(){
    122     cin >> n;
    123 
    124     /* 
    125     Divide Grid into Quandrants as follows:
    126     1 | 2
    127     -----
    128     3 | 4
    129     */
    130 
    131     int fill = 0;
    132     for(int i = 0; i < n/2; i++){
    133         for(int j = 0; j < n/2; j++){
    134 
    135             grid[i][j]              = 4*fill + 1;   // 1st quadrant
    136             grid[i][j + n/2]        = 4*fill + 2;   // 2nd quadrant
    137             grid[i + n/2][j]        = 4*fill + 3;   // 3rd quadrant
    138             grid[i + n/2][j + n/2]  = 4*fill;       // 4th quadrant
    139             
    140             fill++;
    141 
    142         }
    143     }
    144     for(int i = 0; i < n; i++){
    145         for(int j = 0; j < n; j++){
    146             cout << grid[i][j] << " ";
    147         }
    148         cout << endl;
    149     }
    150 }
    151 
    152 signed main(){
    153     int tests = 1;
    154     // cin >> tests;
    155     for(int i = 1; i <= tests; i++) run();
    156     return 0;
    157 }
    158 ```
    159 
    160 ### [1208D — Restore Permutation](https://codeforces.com/contest/1208/problem/D)
    161 
    162 ##### **Approach 1**
    163 
    164 Let us fill the array with numbers from $1$ to $N$ in increasing order.
    165 
    166 $1$ will lie at the last index $i$ such that $s_{i} = 0$. Find and remove this index $i$ from the array and for all indices greater than $i$, reduce their $s_{i}$ values by $1$. Repeat this process for numbers $2, 3, ...N$. In the $i^{th}$ turn, reduce the elements by $i$.
    167 
    168 To find the last index with value zero, we can use segment tree to get range minimum query with lazy propagation.
    169 
    170 Time complexity: $O(N \cdot log(N))$
    171 
    172 **Code**
    173 
    174 ```
    175 #pragma GCC optimize("Ofast")
    176 #include <iostream>
    177 #include <vector>
    178 #include <map>
    179 #include <set>
    180 #include <queue>
    181 #include <algorithm>
    182 #include <string>
    183 #include <cmath>
    184 #include <cstdio>
    185 #include <iomanip>
    186 #include <fstream>
    187 #include <cassert>
    188 #include <cstring>
    189 #include <unordered_set>
    190 #include <unordered_map>
    191 #include <numeric>
    192 #include <ctime>
    193 #include <bitset>
    194 #include <complex>
    195 
    196 using namespace std;
    197 
    198 typedef long long ll;
    199 
    200 const ll INF = 1e16 + 239;
    201 const int MAXN = 1e6 + 239;
    202 
    203 ll a[MAXN];
    204 
    205 namespace SegmentTree {
    206 	int n;
    207 	ll t[4 * MAXN];
    208 	ll mod[4 * MAXN];
    209 
    210 	void pull(int v) {
    211 		t[v] = min(t[2 * v + 1], t[2 * v + 2]);
    212 	}
    213 
    214 	void apply(int v, ll val) {
    215 		t[v] += val;
    216 		mod[v] += val;
    217 	}
    218 
    219 	void push(int v) {
    220 		if (mod[v] != 0) {
    221 			apply(2 * v + 1, mod[v]);
    222 			apply(2 * v + 2, mod[v]);
    223 			mod[v] = 0;
    224 		}
    225 	}
    226 
    227 	void build(int v, int l, int r) {
    228 		if (l + 1 == r) {
    229 			t[v] = a[l];
    230 		} else {
    231 			int m = (r + l) >> 1;
    232 			build(2 * v + 1, l, m);
    233 			build(2 * v + 2, m, r);
    234 			pull(v);
    235 		}
    236 	}
    237 
    238 	void add(int v, int l, int r, int ql, int qr, ll val) {
    239 		if (r <= ql || qr <= l) {
    240 			return;
    241 		} else if (ql <= l && r <= qr) {
    242 			apply(v, val);
    243 		} else {
    244 			push(v);
    245 			int m = (r + l) >> 1;
    246 			add(2 * v + 1, l, m, ql, qr, val);
    247 			add(2 * v + 2, m, r, ql, qr, val);
    248 			pull(v);
    249 		}
    250 	}
    251 
    252 	int go_down(int v, int l, int r) {
    253 		if (l + 1 == r) {
    254 			return l;
    255 		} else {
    256 			push(v);
    257 			int m = (r + l) >> 1;
    258 			int res = -1;
    259 			if (t[2 * v + 2] == 0) {
    260 				res = go_down(2 * v + 2, m, r);
    261 			} else {
    262 				res = go_down(2 * v + 1, l, m);
    263 			}
    264 			pull(v);
    265 			return res;
    266 		}
    267 	}
    268 
    269 	void init(int n_) {
    270 		n = n_;
    271 		build(0, 0, n);
    272 	}
    273 
    274 	void add(int l, int r, ll val) {
    275 		add(0, 0, n, l, r, val);
    276 	}
    277 
    278 	void add(int pos, ll val) {
    279 		add(0, 0, n, pos, pos + 1, val);
    280 	}
    281 
    282 	int last_zero() {
    283 		return go_down(0, 0, n);
    284 	}
    285 }
    286 
    287 signed main() {
    288 	ios_base::sync_with_stdio(false);
    289 	cin.tie(0);
    290 
    291 	int n;
    292 	cin >> n;
    293 	for (int i = 0; i < n; i++) {
    294 		cin >> a[i];
    295 	}
    296 	SegmentTree::init(n);
    297 	vector<int> ans(n, -1);
    298 	for (int i = 1; i <= n; i++) {
    299 		int pos = SegmentTree::last_zero();
    300 		ans[pos] = i;
    301 		SegmentTree::add(pos, INF);
    302 		SegmentTree::add(pos + 1, n, -i);
    303 	}
    304 	for (auto t : ans) {
    305 		cout << t << ' ';
    306 	}
    307 	cout << endl;
    308 }
    309 ```
    310 
    311 ##### **Approach 2**
    312 
    313 For every i from $N$ to 1, let's say the value of the $s_{i}$ is x. So it means there are $k$ smallest unused numbers whose sum is $x$. We simply put the $k+1$st number in the output permutation at this $i$, and continue to move left. This can be implemented using BIT and binary lifting.
    314 
    315 Thanks to [izoomrood](/profile/izoomrood "Expert izoomrood") for expressing the solution in the above words.
    316 
    317 **Code**
    318 
    319 ```
    320 #include<bits/stdc++.h>
    321 using namespace std;
    322 
    323 const int N = 2e5 + 5;
    324 long long BIT[N], s[N];
    325 int n;
    326 int ans[N];
    327 
    328 void update(int x, int delta){
    329       for(; x <= n; x += x&-x)
    330         BIT[x] += delta;
    331 }
    332 
    333 long long query(int x){
    334      long long sum = 0;
    335      for(; x > 0; x -= x&-x)
    336         sum += BIT[x];
    337      return sum;
    338 }
    339 
    340 int searchNumber(long long prefSum){
    341 
    342     int num = 0;
    343     long long sum = 0;
    344     for(int i = 21; i>=0 ; --i){
    345         if((num + (1<<i) <= n) && (sum + BIT[num + (1<<i)] <= prefSum)){
    346             num += (1<<i);
    347             sum += BIT[num];
    348         }
    349     }
    350     return num + 1;
    351 }
    352 
    353 int main(){
    354 	scanf("%d",&n);
    355 	for(int i = 1; i <= n; ++i){
    356         update(i, i);
    357 		scanf("%lld", &s[i]);
    358 	}
    359 	for(int i = n; i >= 1; --i){
    360         ans[i] = searchNumber(s[i]);
    361         update(ans[i], -ans[i]);
    362     } 
    363     for(int i = 1; i <= n; ++i){
    364         printf("%d", ans[i]);
    365         if(i < n){
    366             printf(" ");
    367         }
    368         else printf("\n");
    369     }
    370 }
    371 ```
    372 
    373 ### [1208E — Let them slide](https://codeforces.com/contest/1208/problem/E)
    374 
    375 For every array $i$ from $1$ to $N$, let us maintain 2 pointers $L[i]$ and $R[i]$, representing the range of elements in $i_{th}$ array, that can be accessed by the current column index $j$.
    376 
    377 Initially all $L[i]$ and $R[i]$ would be set equal to 0.
    378 
    379 As we move from $j_{th}$ index to $(j+1)_{th}$ index, some $L[i]$ and $R[i]$ would change. Specifically, all those arrays which have $size \ge min(j,W-j-1)$ would have their $L[i]$ and $R[i]$ change.
    380 
    381 Since overall movement of $L[i]$ and $R[i]$ would be equal to $2 \cdot$ size_of_array($i$). Overall change would be of order of $O(\sum a[i])$. For every array we need range max query in $(L[i], R[i])$.
    382 
    383 We can use multisets/ segment trees/ deques to update the answers corresponding to an array if its $L[i], R[i]$ changes. This way we can get complexity $O(N)$ or $O(N \cdot log(N))$ depending upon implementation.
    384 
    385 **Code**
    386 
    387 ```
    388 #include<bits/stdc++.h>
    389 using namespace std;
    390 
    391 const int N = 1e6 + 5;
    392 long long ans[N];
    393 vector<pair<int, int> > add_element[N], remove_element[N];
    394 multiset<int> global_ms[N];
    395 
    396 int main(){
    397 	int n,w;
    398 	scanf("%d %d", &n, &w);
    399 	for(int i = 0; i < n; ++i){
    400 		int cnt;
    401 		scanf("%d", &cnt);
    402 		for(int j = 0; j < cnt; ++j){
    403 			int x,l,r;
    404 			scanf("%d", &x);
    405 			add_element[j].push_back(make_pair(x, i));
    406 			remove_element[j + w - cnt].push_back(make_pair(x, i));
    407 		}
    408 		if(cnt < w){
    409 			add_element[cnt].push_back(make_pair(0, i));
    410 			remove_element[w - 1].push_back(make_pair(0, i));
    411 			add_element[0].push_back(make_pair(0, i));
    412 			remove_element[w - 1 - cnt].push_back(make_pair(0, i));
    413 		}
    414 	}
    415 	for(int i = 0; i < w; ++i){
    416 
    417 		for(auto j:add_element[i]){
    418 			int idx = j.second;
    419 			int val = j.first;
    420 			ans[i] -= (global_ms[idx].empty()? 0: *global_ms[idx].rbegin());
    421 			global_ms[idx].insert(val);
    422 			ans[i] += *global_ms[idx].rbegin();
    423 		}	
    424 
    425 		if(i < w - 1){
    426 			ans[i + 1] = ans[i];
    427 			for(auto j:remove_element[i]){
    428 				int idx = j.second;
    429 				int val = j.first;
    430 				ans[i + 1] -= (*global_ms[idx].rbegin());
    431 				global_ms[idx].erase(global_ms[idx].find(val));
    432 				ans[i + 1] += (global_ms[idx].empty()? 0: *global_ms[idx].rbegin());
    433 			}
    434 		}
    435 		printf("%lld ",ans[i]);
    436 	}
    437 	printf("\n");
    438 }
    439 ```
    440 
    441 ### [1208F — Bits And Pieces](https://codeforces.com/contest/1208/problem/F)
    442 
    443 The idea is to first fix some $a[i]$ and try to get the bits which are off in $a[i]$ from any $2$ elements to the right of $i$. Since, we need to maximize the value, we will try to get higher bits first. What we need now is, for every number $x$ from $0$ to $2^{21}-1$, the $2$ right most positions such that the bits present in $x$ are also present in the elements on those positions. This can be done by iterating over submasks(slow) or SOS-DP(fast).
    444 
    445 Once we process the positions for every $x$, let us fix some $a[i]$ and iterate over the bits which are off in $a[i]$ from the highest to the lowest. Lets say the current maximum we have got is $w$ and we are going to consider the $y^{th}$ bit. We can get this bit if the $2$ positions for $w|2^{y}$ are to the right of $i$ else we can not.
    446 
    447 The final answer would be the maximum of $a[i]|w$ over all $i$ from $1$ to $N$.
    448 
    449 Time complexity $O((M+N)\cdot logM)$ where $M$ is the max element in the array.
    450 
    451 **Code**
    452 
    453 ```
    454 #include <bits/stdc++.h>
    455 
    456 #define ll          long long
    457 #define pb          push_back
    458 #define pii         pair<int,int>
    459 #define vi          vector<int>
    460 #define vii         vector<pii>
    461 #define mi          map<int,int>
    462 #define mii         map<pii,int>
    463 #define all(a)      (a).begin(),(a).end()
    464 #define x           first
    465 #define y           second
    466 #define sz(x)       (int)x.size()
    467 #define endl        '\n'
    468 #define hell        1000000007
    469 #define rep(i,a,b)  for(int i=a;i<b;i++)
    470 using namespace std;
    471 
    472 int n,a[1000006],ans,bits;
    473 pii dp[1<<21];
    474 
    475 void add(int mask,int w){
    476     if(dp[mask].x==-1) dp[mask].x=w;
    477     else if(dp[mask].y==-1){
    478         if(dp[mask].x==w) return;
    479         dp[mask].y=w;
    480         if(dp[mask].x>dp[mask].y) swap(dp[mask].x,dp[mask].y);
    481     }
    482     else{
    483         if(dp[mask].y<w){
    484             dp[mask].x=dp[mask].y;
    485             dp[mask].y=w;
    486         }
    487         else if(dp[mask].x<w and dp[mask].y!=w) dp[mask].x=w;
    488     }
    489 }
    490 
    491 void merge(int m1,int m2){
    492     if(dp[m2].x!=-1) add(m1,dp[m2].x);
    493     if(dp[m2].y!=-1) add(m1,dp[m2].y);
    494 }
    495 
    496 void solve(){
    497 	memset(dp,-1,sizeof dp);
    498     cin>>n;
    499     rep(i,0,n){
    500         cin>>a[i];
    501         add(a[i],i);
    502         bits=max((int)log2(a[i]),bits);
    503     }
    504     bits++;
    505     rep(i,0,bits){
    506         rep(mask,0,1<<bits){
    507             if(mask&(1<<i)){
    508                 merge(mask^(1<<i),mask);
    509             }
    510         }
    511     }
    512     rep(i,0,n){
    513         int cur=(1<<bits)-1-a[i];
    514         int opt=0;
    515         for(int j=bits-1;j>=0;j--){
    516             if((cur>>j)&1){
    517                 if(dp[opt^(1<<j)].y!=-1 and dp[opt^(1<<j)].x>i){
    518                     opt^=(1<<j);
    519                 }
    520             }
    521         }
    522         if(dp[opt].y!=-1 and dp[opt].x>i) ans=max(ans,a[i]^opt);
    523     }
    524     cout<<ans<<endl;
    525 }
    526 
    527 signed main(){
    528     ios::sync_with_stdio(false);
    529     cin.tie(0);
    530     cout.tie(0);
    531     int t=1;
    532     // cin>>t;
    533     while(t--){
    534         solve();
    535     }
    536     return 0;
    537 }
    538 ```
    539 
    540 ### [1208G — Polygons](https://codeforces.com/contest/1208/problem/G)
    541 
    542 If we choose a polygon with side length $l$, it is profitable to choose polygons with side lengths as divisors of $l$ as well, because this will not increase the answer.
    543 
    544 So our final set would be such that for every polygon with side length $l$, we would have polygons with side length as divisors of $l$ as well.
    545 
    546 All polygons should have at least one common point in the final arrangement, say $P$ or else we can rotate them and get such $P$. For formal proof, please refer [this comment](https://codeforces.com/blog/entry/69357?#comment-538545) by [orz](/profile/orz "International Master orz").
    547 
    548 Let us represent points on the circle as the distance from point $P$. Like for $k$ sided polygon, $0$,$\frac{1}{k} ,\frac{2}{k} ,…\frac{k-1}{k}$.
    549 
    550 Now the number of unique fractions over all the polygons would be our answer, which is equal to sum of $ \phi (l)$ over all side lengths $l$ of the polygons because for $l$ sided polygon there will be $\phi(l)$ extra points required by it as compared to its divisors.
    551 
    552 One observation to get to the final solution is $\phi(l) \ge \phi(divisor(l))$. So, we can sort the side lengths by their $\phi$ values and take the smallest $k$ of them. This will minimize the number of points as well as satisfy the property of our set.
    553 
    554 **NOTE:** We can not consider polygon of side length $2$. This can be handled easily.
    555 
    556 **Code**
    557 
    558 ```
    559 #include <bits/stdc++.h>
    560 using namespace std;
    561 int phi[1000006];
    562 void process_phis(int n){
    563     iota(phi,phi+n+1,0);
    564     for(int i = 2 ; i<=n;i++){
    565         if(phi[i]==i){
    566             phi[i]=i-1;
    567             for(int j=2*i;j<=n;j+=i){
    568                 phi[j]=(phi[j]/i)*(i-1);
    569             }
    570         }
    571     }
    572 }
    573 int main(){
    574     int n,k;
    575     cin>>n>>k;
    576     if(k==1){
    577         cout<<3<<endl;
    578         return 0;
    579     }
    580     process_phis(n);
    581     k+=2;
    582     sort(phi+1,phi+n+1);
    583     cout<<accumulate(phi+1,phi+k+1,0LL)<<endl;
    584     return 0;
    585 }
    586 ```
    587 
    588 Tutorial is loading...
    589 
    590 **Code**
    591 
    592 ```
    593 /**
    594  * This line was copied from template
    595  * This is nk_sqrt_300.cpp
    596  * 
    597  * @author: Nikolay Kalinin
    598  * @date: Fri, 23 Aug 2019 22:28:23 +0300
    599  */
    600 #include <bits/stdc++.h>
    601 
    602 using namespace std;
    603 
    604 #ifdef LOCAL
    605     #define eprintf(...) fprintf(stderr, __VA_ARGS__)
    606 #else
    607     #define eprintf(...) 42
    608 #endif
    609 
    610 using ll = long long;
    611 using ld = long double;
    612 using D = double;
    613 using uint = unsigned int;
    614 template<typename T>
    615 using pair2 = pair<T, T>;
    616 using pii = pair<int, int>;
    617 using pli = pair<ll, int>;
    618 using pll = pair<ll, ll>;
    619 
    620 #define pb push_back
    621 #define mp make_pair
    622 #define all(x) (x).begin(),(x).end()
    623 #define fi first
    624 #define se second
    625 
    626 const int maxn = 100005;
    627 const int infk = maxn;
    628 
    629 const int BSZ = 700;
    630 
    631 vector<int> gr[maxn];
    632 vector<int> dead_ends[maxn];
    633 int th[maxn][2];
    634 int threshold[maxn];
    635 int up[maxn], fastup[maxn];
    636 bool isleaf[maxn];
    637 int curcnt[maxn];
    638 int was[maxn];
    639 int curk, curkid;
    640 int n;
    641 int timer;
    642 int c[maxn];
    643 bool isinteresting[maxn];
    644 vector<int> interesting;
    645 pair2<int> qs[BSZ];
    646 vector<int> at[2 * BSZ];
    647 queue<int> q;
    648 int path[maxn];
    649 vector<int> ks;
    650 vector<int> cntdead[2 * BSZ];
    651 int intid[maxn];
    652 vector<int> order;
    653 int newid[maxn];
    654 vector<int> grinit[maxn];
    655 int compk[2 * infk + 5];
    656 
    657 void leavedesc(int cur, int pr)
    658 {
    659     newid[cur] = order.size();
    660     up[newid[cur]] = newid[pr];
    661     order.pb(cur);
    662     for (int i = 0; i < (int)grinit[cur].size(); i++)
    663     {
    664         if (grinit[cur][i] == pr)
    665         {
    666             swap(grinit[cur][i], grinit[cur].back());
    667             grinit[cur].pop_back();
    668             i--;
    669         } else
    670         {
    671             leavedesc(grinit[cur][i], cur);
    672         }
    673     }
    674 }
    675 
    676 inline void computecolor(int cur)
    677 {
    678     if (was[cur] != timer) curcnt[cur] = 0;
    679     int cntred = curcnt[cur];
    680     cntred += (int)cntdead[intid[cur]].size() <= curkid ? cntdead[intid[cur]].back() : cntdead[intid[cur]][curkid];
    681     int cntblue = (int)gr[cur].size() - cntred;
    682     if (cntblue - cntred >= curk) c[cur] = 1;
    683     else c[cur] = 0;
    684 }
    685 
    686 inline void pushtoparent(int cur)
    687 {
    688     if (cur == 0) return;
    689     int par = fastup[cur];
    690     
    691     int colorup = 1 - (curk >= th[cur][c[cur]]);
    692     
    693     if (was[par] != timer)
    694     {
    695         was[par] = timer;
    696         curcnt[par] = 0;
    697     }
    698     curcnt[par] += 1 - colorup;
    699 }
    700 
    701 int main()
    702 {
    703     scanf("%d%d", &n, &curk);
    704     for (int i = 0; i < n - 1; i++)
    705     {
    706         int u, v;
    707         scanf("%d%d", &u, &v);
    708         u--, v--;
    709         grinit[u].pb(v);
    710         grinit[v].pb(u);
    711     }
    712     leavedesc(0, -1);
    713     
    714     for (int i = 0; i < n; i++)
    715     {
    716         for (auto t : grinit[i]) gr[newid[i]].pb(newid[t]);
    717     }
    718     
    719     for (int i = 0; i < n; i++) scanf("%d", &c[newid[i]]);
    720         
    721     for (int i = 0; i < n; i++) if (c[i] != -1) isleaf[i] = true;
    722     int nq;
    723     scanf("%d", &nq);
    724     for (int lq = 0; lq < nq; lq += BSZ)
    725     {
    726         int rq = min(nq, lq + BSZ);
    727         memset(isinteresting, 0, sizeof isinteresting);
    728         ks.clear();
    729         ks.pb(curk);
    730         for (int q = lq; q < rq; q++)
    731         {
    732             int t;
    733             scanf("%d", &t);
    734             if (t == 1)
    735             {
    736                 int v;
    737                 scanf("%d", &v);
    738                 v--;
    739                 v = newid[v];
    740                 isinteresting[v] = true;
    741                 qs[q - lq] = {v, -1};
    742             } else if (t == 2)
    743             {
    744                 int v, newc;
    745                 scanf("%d%d", &v, &newc);
    746                 v--;
    747                 v = newid[v];
    748                 isinteresting[v] = true;
    749                 qs[q - lq] = {v, newc};
    750             } else
    751             {
    752                 int newk;
    753                 scanf("%d", &newk);
    754                 qs[q - lq] = {-1, newk};
    755                 ks.pb(newk);
    756             }
    757         }
    758         
    759         sort(all(ks));
    760         ks.resize(unique(all(ks)) - ks.begin());
    761         int kssz = ks.size();
    762         ks.pb(infk);
    763         int curcompkid = 0;
    764         for (int i = -infk; i <= infk; i++)
    765         {
    766             compk[i + infk] = curcompkid;
    767             if (curcompkid < kssz && ks[curcompkid] == i) curcompkid++;
    768         }
    769 
    770         isinteresting[0] = true;
    771         interesting.clear();
    772 
    773         for (int i = 0; i <= kssz; i++) at[i].clear();
    774 
    775         for (int cur = 0; cur < n; cur++)
    776         {
    777             dead_ends[cur].clear();
    778             path[cur] = -1;
    779             if (isinteresting[cur])
    780             {
    781                 path[cur] = -2;
    782             }
    783         }
    784 
    785         for (int cur = n - 1; cur >= 0; cur--)
    786         {
    787             int ret = -1;
    788             if (isinteresting[cur])
    789             {
    790                 intid[cur] = interesting.size();
    791                 interesting.pb(cur);
    792                 cntdead[intid[cur]].clear();
    793                 cntdead[intid[cur]].pb(0);
    794             }
    795             if (path[cur] == -1)
    796             {
    797                 if (isleaf[cur])
    798                 {
    799                     if (c[cur] == 0) at[compk[-infk + infk]].pb(cur);
    800                     else at[compk[infk + infk]].pb(cur);
    801                 } else
    802                 {
    803                     curcnt[cur] = 0;
    804                     int cntred = 0;
    805                     int cntblue = gr[cur].size();
    806                     at[compk[cntblue - cntred + 1 + infk]].pb(cur);
    807                 }
    808             } else if (path[cur] == -2)
    809             {
    810                 ret = cur;
    811             } else
    812             {
    813                 ret = path[cur];
    814             }
    815             if (cur == 0) break;
    816             if (ret == -1) continue;
    817             
    818             if (path[up[cur]] == -1) path[up[cur]] = ret;
    819             else if (path[up[cur]] >= 0)
    820             {
    821                 isinteresting[up[cur]] = true;
    822                 fastup[path[up[cur]]] = up[cur];
    823                 fastup[ret] = up[cur];
    824                 path[up[cur]] = -2;
    825             } else
    826             {
    827                 fastup[ret] = up[cur];
    828             }
    829         }
    830         
    831         timer++;
    832         for (int i = 0; i <= kssz; i++)
    833         {
    834             for (auto t : at[i]) q.push(t);
    835             while (!q.empty())
    836             {
    837                 int cur = q.front();
    838                 q.pop();
    839                 if (was[cur] == timer) continue;
    840                 was[cur] = timer;
    841                 if (path[up[cur]] == -1)
    842                 {
    843                     curcnt[up[cur]]++;
    844                     int cntred = curcnt[up[cur]];
    845                     int cntblue = gr[up[cur]].size() - cntred;
    846                     if (cntblue - cntred + 1 <= ks[i]) q.push(up[cur]);
    847                     else at[compk[cntblue - cntred + 1 + infk]].pb(up[cur]);
    848                 } else if (path[up[cur]] == -2)
    849                 {
    850                     int id = intid[up[cur]];
    851                     while ((int)cntdead[id].size() <= i) cntdead[id].pb(cntdead[id].back());
    852                     cntdead[id].back()++;
    853                 } else { // in path
    854                     dead_ends[up[cur]].pb(ks[i]);
    855                 }
    856             }
    857         }
    858         
    859         for (int cur = n - 1; cur >= 0; cur--) if (path[cur] != -1)
    860         {
    861             int cntchildren = gr[cur].size();
    862             if (path[cur] == -2)
    863             {
    864                 th[cur][0] = -infk;
    865                 th[cur][1] = +infk;
    866             } else
    867             {
    868                 th[cur][0] = cntchildren + 1;
    869                 th[cur][1] = cntchildren + 1;
    870                 th[cur][0] = min(th[cur][0], max(th[path[cur]][0], cntchildren - 1 - 1 + 1));
    871                 th[cur][1] = min(th[cur][1], max(th[path[cur]][1], cntchildren - 1 - 1 + 1));
    872                 for (int i = 0; i < (int)dead_ends[cur].size(); i++)
    873                 {
    874                     int cntred = i + 1;
    875                     int cntblue = cntchildren - cntred;
    876                     th[cur][0] = min(th[cur][0], max(dead_ends[cur][i], cntblue - cntred + 1));
    877                     th[cur][1] = min(th[cur][1], max(dead_ends[cur][i], cntblue - cntred + 1));
    878         
    879                     cntred = i + 1 + 1;
    880                     cntblue = cntchildren - cntred;
    881                     th[cur][0] = min(th[cur][0], max(max(th[path[cur]][0], dead_ends[cur][i]), cntblue - cntred + 1));
    882                     th[cur][1] = min(th[cur][1], max(max(th[path[cur]][1], dead_ends[cur][i]), cntblue - cntred + 1));
    883                 }
    884                 th[path[cur]][0] = th[cur][0];
    885                 th[path[cur]][1] = th[cur][1];
    886             }
    887         }
    888         
    889         
    890         ::curkid = lower_bound(all(ks), curk) - ks.begin();
    891         for (int q = 0; q < rq - lq; q++)
    892         {
    893             timer++;
    894             if (qs[q].fi == -1)
    895             {
    896                 curk = qs[q].se;
    897                 ::curkid = lower_bound(all(ks), curk) - ks.begin();
    898             } else if (qs[q].se != -1) c[qs[q].fi] = qs[q].se;
    899             else
    900             {
    901                 for (auto v : interesting)
    902                 {
    903                     if (!isleaf[v]) computecolor(v);
    904                     pushtoparent(v);
    905                 }
    906                 printf("%d\n", c[qs[q].fi]);
    907             }
    908         }
    909     }
    910     return 0;
    911 }
    912 ```