codeforces-scrape

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

1017.md (28369B)


      1 Source: https://codeforces.com/blog/entry/61081
      2 
      3 Tutorial is loading...
      4 
      5 **Solution(arsijo)**
      6 
      7 ```
      8 #include <bits/stdc++.h>
      9 using namespace std;
     10 
     11 int main()
     12 {
     13     int n;
     14 	cin >> n;
     15 	int a, b, c, d;
     16 	cin >> a >> b >> c >> d;
     17 	int S = a + b + c + d;
     18 	int Ans = 1;
     19 	for(int i = 2; i <= n; i++)
     20 	{
     21 	    cin >> a >> b >> c >> d;
     22 	    if(a + b + c + d > S)
     23 	    {
     24 	        Ans++;
     25 	    }
     26 	}
     27 	printf("%d\n",Ans);
     28 	return 0;
     29 }
     30 ```
     31 
     32 Tutorial is loading...
     33 
     34 **Solution(arsijo)**
     35 
     36 ```
     37 #include <bits/stdc++.h>
     38 using namespace std;
     39 
     40 long long ar[4];
     41 char c1[4] = {'0', '0', '1', '1'};
     42 char c2[4] = {'0', '1', '0', '1'};
     43 
     44 int main() {
     45     int n;
     46     cin >> n;
     47     string a, b;
     48     cin >> a >> b;
     49     for(int i = 0; i < n; i++){
     50         for(int j = 0; j < 4; j++){
     51             if(c1[j] == a[i] && c2[j] == b[i]){
     52                 ar[j]++;
     53             }
     54         }
     55     }
     56     cout << ar[0] * ar[2] + ar[0] * ar[3] + ar[1] * ar[2] << endl;
     57     return 0;
     58 }
     59 ```
     60 
     61 Tutorial is loading...
     62 
     63 **Solution(Magolor)**
     64 
     65 ```
     66 #include <bits/stdc++.h>
     67 using namespace std;
     68 #define MAXN 100000
     69 #define rint register int
     70 inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
     71 int n, L, A[MAXN+5];
     72 int main()
     73 {
     74 	n = rf();
     75 	L = (int)sqrt(n);
     76 	for(rint i = 1, o = n, j; i <= n; i += L)
     77 		for(j = min(i+L-1,n); j >= i; A[j--] = o--);
     78 	for(rint i = 1; i <= n; i++)
     79 		printf("%d%c",A[i],"\n "[i<n]);
     80 	return 0;
     81 }
     82 ```
     83 
     84 Tutorial is loading...
     85 
     86 **Solution(Magolor)**
     87 
     88 ```
     89 #include <bits/stdc++.h>
     90 using namespace std;
     91 #define MAXN 100000
     92 #define rint register int
     93 inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
     94 int Wu[4096], f[64][64][104], g[4096][104], w[16], m, n, q, E, K, B = 6, L = 63, H = 4032; char _[16];
     95 int main()
     96 {
     97 	m = rf();
     98 	n = rf();
     99 	q = rf();
    100 	generate(w,w+m,rf);
    101 	E = 1<<m;
    102 	for(rint S = 0, j; S < E; S++)
    103 	{
    104 		for(j = 0; j < m; j++)
    105 			S&1<<j?:Wu[S]+=w[j];
    106 		Wu[S] = min(Wu[S],101);
    107 	}
    108 	for(rint i = 1, j, S; i <= n; i++)
    109 	{
    110 		scanf("%s",_+1);
    111 		for(S = 0, j = m; j; j--)
    112 			S = S<<1|(_[j]^'0');
    113 		for(j = 0; j < 64; j++)
    114 			++f[(S&H)>>B][j][Wu[((j^(S&L))|H)&~-E]];
    115 	}
    116 	for(rint S = 0, a, b, j; S < E; S++)
    117 	{
    118 		for(j = 0; j < 64; j++)
    119 			for(a = 0, b = Wu[(((j<<B)^(S&H))|L)&~-E]; b <= 100; a++, b++)
    120 				g[S][b] += f[j][S&L][a];
    121 		partial_sum(g[S],g[S]+101,g[S]);
    122 	}
    123 	for(rint i = 1, j, S; i <= q; i++)
    124 	{
    125 		scanf("%s",_+1);
    126 		for(S = 0, j = m; j; j--)
    127 			S = S<<1|(_[j]^'0');
    128 		printf("%d\n",g[S][rf()]);
    129 	}
    130 	return 0;
    131 }
    132 ```
    133 
    134 Tutorial is loading...
    135 
    136 **Solution(Magolor)**
    137 
    138 ```
    139 #include <bits/stdc++.h>
    140 using namespace std;
    141 #define ll long long
    142 #define rint register int
    143 inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
    144 //=====Computational Geometry Definitions
    145 struct Vec
    146 {
    147 	int x,y; Vec(){} Vec(int _x, int _y){x=_x,y=_y;} inline Vec operator + (Vec b){return Vec(x+b.x,y+b.y);}
    148 	inline Vec operator - (Vec b){return Vec(x-b.x,y-b.y);} inline Vec operator - (){return Vec(-x,-y);}
    149 	inline ll operator * (Vec b){return (ll)x*b.x+(ll)y*b.y;} inline ll operator % (Vec b){return (ll)x*b.y-(ll)b.x*y;}
    150 	inline ll operator ~ (){return (ll)x*x+(ll)y*y;} inline bool operator < (const Vec &b)const{return x^b.x?x<b.x:y<b.y;}
    151 	inline bool operator ==(Vec b){return x==b.x&&y==b.y;} inline bool operator !=(Vec b){return x^b.x||y^b.y;}
    152 };	typedef Vec Pt; inline bool ToLeft(Vec a, Vec b){return b%a>0;} inline bool Para(Vec a, Vec b){return !(a%b);}
    153 Pt LTL; inline bool cmpltl(Pt a, Pt b){a = a-LTL; b = b-LTL; return Para(a,b) ? ~a<~b : ToLeft(b,a);}
    154 typedef vector<Pt> Poly; Poly A, B, C, D; typedef vector<ll> Str; Str T, S; int n, m; vector<int> nex;
    155 //=====
    156 void CH(Poly &A, Poly &R)
    157 {
    158 	R.push_back(Pt());
    159 	LTL = *min_element(A.begin(),A.end());
    160 	sort(A.begin(),A.end(),cmpltl);
    161 	for(rint i = 0; i < (int)A.size(); i++)
    162 	{
    163 		for(; R.size()>2&&!ToLeft(A[i]-R.back(),R.back()-R[R.size()-2]); )
    164 			R.pop_back();
    165 		R.push_back(A[i]);
    166 	}
    167 	R[0] = R[R.size()-1];
    168 	R.push_back(R[1]);
    169 }
    170 void CTOS(Poly &p, Str &s)
    171 {
    172 	s.push_back(0);
    173 	for(rint i = 1; i < (int)p.size()-1; i++)
    174 	{
    175 		s.push_back(~(p[i]-p[i-1]));
    176 		s.push_back((p[i]-p[i-1])%(p[i+1]-p[i]));
    177 	}
    178 }
    179 void CalNex()
    180 {
    181 	nex.resize(m+1);
    182 	for(rint i = 2, j = 1; i <= m; i++)
    183 	{
    184 		for(; j>1&&S[i]^S[j]; )
    185 			j = nex[j-1]+1;
    186 		j += S[i]==S[j];
    187 		nex[i] = j-1;
    188 	}
    189 }
    190 bool KMP()
    191 {
    192 	for(rint i = 1, j = 1; i <= n; i++)
    193 	{
    194 		for(; j>1&&(j>m||T[i]^S[j]); )
    195 			j = nex[j-1]+1;
    196 		j+=T[i]==S[j]; 
    197 		if(j>m)
    198 			return true;
    199 	}
    200 	return false;
    201 }
    202 int main()
    203 {
    204 	A.resize(rf()); B.resize(rf());
    205 	for(rint i = 0, s = (int)A.size(); i < s; i++)
    206 		A[i].x = rf(), A[i].y = rf();
    207 	CH(A,C);
    208 	CTOS(C,T);
    209 	n = T.size()-1;
    210 	for(rint i = 0, s = (int)B.size(); i < s; i++)
    211 		B[i].x = rf(), B[i].y = rf();
    212 	CH(B,D);
    213 	CTOS(D,S);
    214 	m = S.size()-1;
    215 	for(rint i = 1, s = (int)T.size(); i < s; i++)
    216 		T.push_back(T[i]);
    217 	n <<= 1;
    218 	CalNex();
    219 	puts(KMP()?"YES":"NO");
    220 	return 0;
    221 }
    222 ```
    223 
    224 **Solution(Kostroma)**
    225 
    226 ```
    227 #pragma comment(linker, "/STACK:512000000")
    228 #define _CRT_SECURE_NO_WARNINGS
    229 //#include "testlib.h"
    230 #include <bits/stdc++.h>
    231 using namespace std;
    232 
    233 #define all(a) a.begin(), a.end()
    234 using li = long long;
    235 using ld = long double;
    236 void solve(bool);
    237 void precalc();
    238 clock_t start;
    239 int main() {
    240 #ifdef AIM
    241   freopen("/home/alexandero/CLionProjects/ACM/input.txt", "r", stdin);
    242 //freopen("/home/alexandero/CLionProjects/ACM/output.txt", "w", stdout);
    243 //freopen("out.txt", "w", stdout);
    244 #else
    245   //freopen("input.txt", "r", stdin);
    246 //freopen("output.txt", "w", stdout);
    247 #endif
    248   start = clock();
    249   int t = 1;
    250 #ifndef AIM
    251   cout.sync_with_stdio(0);
    252   cin.tie(0);
    253 #endif
    254   cout.precision(20);
    255   cout << fixed;
    256 //cin >> t;
    257   precalc();
    258   while (t--) {
    259     solve(true);
    260   }
    261   cout.flush();
    262 
    263 #ifdef AIM1
    264   while (true) {
    265 solve(false);
    266 }
    267 #endif
    268 
    269 #ifdef AIM
    270   cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";
    271 #endif
    272   return 0;
    273 }
    274 
    275 //BE CAREFUL: IS INT REALLY INT?
    276 
    277 template<typename T>
    278 T binpow(T q, T w, T mod) {
    279   if (!w)
    280     return 1 % mod;
    281   if (w & 1)
    282     return q * 1LL * binpow(q, w - 1, mod) % mod;
    283   return binpow(q * 1LL * q % mod, w / 2, mod);
    284 }
    285 
    286 template<typename T>
    287 T gcd(T q, T w) {
    288   while (w) {
    289     q %= w;
    290     swap(q, w);
    291   }
    292   return q;
    293 }
    294 template<typename T>
    295 T lcm(T q, T w) {
    296   return q / gcd(q, w) * w;
    297 }
    298 
    299 template <typename T>
    300 void make_unique(vector<T>& vec) {
    301   sort(all(vec));
    302   vec.erase(unique(all(vec)), vec.end());
    303 }
    304 
    305 template<typename T>
    306 void relax_min(T& cur, T val) {
    307   cur = min(cur, val);
    308 }
    309 
    310 template<typename T>
    311 void relax_max(T& cur, T val) {
    312   cur = max(cur, val);
    313 }
    314 
    315 void precalc() {
    316 
    317 }
    318 
    319 #define int li
    320 //const li mod = 1000000007;
    321 //using ull = unsigned long long;
    322 
    323 struct Point {
    324   int x, y;
    325   Point() {}
    326   Point(int x, int y) : x(x), y(y) {}
    327   Point operator - (const Point& ot) const {
    328     return Point(x - ot.x, y - ot.y);
    329   }
    330   int operator * (const Point& ot) const {
    331     return x * ot.y - y * ot.x;
    332   }
    333   void scan() {
    334     cin >> x >> y;
    335   }
    336   bool operator < (const Point& ot) const {
    337     return make_pair(x, y) < make_pair(ot.x, ot.y);
    338   }
    339   int sqr_len() const {
    340     return x * x + y * y;
    341   }
    342   long double get_len() const {
    343     return sqrtl(sqr_len());
    344   }
    345   int operator % (const Point& ot) const {
    346     return x * ot.x + y * ot.y;
    347   }
    348 };
    349 
    350 struct Polygon {
    351   vector<Point> hull;
    352   Polygon(int n) {
    353     vector<Point> points(n);
    354     for (int i = 0; i < n; ++i) {
    355       points[i].scan();
    356     }
    357     sort(all(points));
    358     vector<Point> up, down;
    359     for (auto& pt : points) {
    360       while (up.size() > 1 && (up[up.size() - 2] - up.back()) * (pt - up.back()) >= 0) {
    361         up.pop_back();
    362       }
    363       up.push_back(pt);
    364       while (down.size() > 1 && (down[down.size() - 2] - down.back()) * (pt - down.back()) <= 0) {
    365         down.pop_back();
    366       }
    367       down.push_back(pt);
    368     }
    369     hull = up;
    370     for (int i = (int)down.size() - 2; i > 0; --i) {
    371       hull.push_back(down[i]);
    372     }
    373   }
    374   int sqr_len(int pos) const {
    375     return (hull[(pos + 1) % hull.size()] - hull[pos]).sqr_len();
    376   }
    377   int size() const {
    378     return (int)hull.size();
    379   }
    380   long double get_angle(int pos) const {
    381     auto a = hull[(pos + 1) % hull.size()] - hull[pos], b = hull[(pos + hull.size() - 1) % hull.size()] - hull[pos];
    382     long double co = (a % b) / a.get_len() / b.get_len();
    383     return co;
    384   }
    385 };
    386 
    387 void solve(bool read) {
    388   vector<Polygon> polys;
    389   int n[2];
    390   cin >> n[0] >> n[1];
    391   for (int i = 0; i < 2; ++i) {
    392     polys.emplace_back(n[i]);
    393   }
    394   if (polys[0].size() != polys[1].size()) {
    395     cout << "NO\n";
    396     return;
    397   }
    398   vector<long double> all_lens;
    399   int m = polys[0].size();
    400   for (int i = 0; i < m; ++i) {
    401     all_lens.push_back(polys[0].sqr_len(i));
    402     all_lens.push_back(polys[0].get_angle(i));
    403   }
    404   all_lens.push_back(-1);
    405   for (int j = 0; j < 2; ++j) {
    406     for (int i = 0; i < m; ++i) {
    407       all_lens.push_back(polys[1].sqr_len(i));
    408       all_lens.push_back(polys[1].get_angle(i));
    409     }
    410   }
    411   /*for (int x : all_lens) {
    412     cout << x << " ";
    413   }
    414   cout << "\n";*/
    415   vector<int> p(all_lens.size());
    416   for (int i = 1; i < p.size(); ++i) {
    417     int j = p[i - 1];
    418     while (j > 0 && all_lens[i] != all_lens[j]) {
    419       j = p[j - 1];
    420     }
    421     if (all_lens[i] == all_lens[j]) {
    422       ++j;
    423     }
    424     p[i] = j;
    425     if (p[i] == 2 * m) {
    426       cout << "YES\n";
    427       return;
    428     }
    429   }
    430   cout << "NO\n";
    431 
    432 }
    433 ```
    434 
    435 Tutorial is loading...
    436 
    437 **Solution(Magolor,optimized by arsijo)**
    438 
    439 ```
    440 #include <bits/stdc++.h>
    441 using namespace std;
    442 #define ll long long
    443 #define uint unsigned int
    444 #define rint register int
    445 inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
    446 bitset<100000032> _b; int n; uint A, B, C, D, Ans;
    447 inline uint f(int p){
    448     return((A*p+B)*p+C)*p+D;
    449 }
    450 inline int cnt(int p, int n){
    451     int r=0;
    452     for(;n/=p;r+=n);
    453     return r;
    454 }
    455 inline auto b(int i)->decltype(_b[0]){
    456     return _b[(i&1)&&(i%6!=3)?i/6<<1|((i%6)>1):0];
    457 }
    458 inline auto b2(int i)->decltype(_b[0]){
    459     return _b[i/6<<1|1];
    460 }
    461 inline auto b3(int i)->decltype(_b[0]){
    462     return _b[i/6<<1];
    463 }
    464 
    465 int main()
    466 {
    467     n = rf();
    468     A = rf();
    469     B = rf();
    470     C = rf();
    471     D = rf();
    472     _b[0] = 1;
    473     Ans = cnt(2,n)*f(2)+cnt(3,n)*f(3);
    474     for(rint i = 5, j, z, c, w; i <= n; i += 4){
    475         if(!b2(i))
    476         {
    477             Ans += cnt(i,n)*f(i);
    478             if(i <= 20000){
    479                 w = i + i;
    480                 c = w % 6;
    481                 z = (i * i) % 6;
    482                 if(c == 0){
    483                     if(z == 1){
    484                         for(j = i * i; j <= n; j += w){
    485                             b3(j) = 1;
    486                         }
    487                     }else if(z == 5){
    488                         for(j = i * i; j <= n; j += w){
    489                             b2(j) = 1;
    490                         }
    491                     }
    492                 }else if(c == 2){
    493                     if(z == 1){
    494                         for(j = i * i; j <= n; j += w){
    495                             b3(j) = 1;
    496                             j += w + w;
    497                             if(j <= n){
    498                                 b2(j) = 1;
    499                             }
    500                         }
    501                     }else if(z == 5){
    502                         for(j = i * i; j <= n; j += w + w){
    503                             b2(j) = 1;
    504                             j += w;
    505                             if(j <= n){
    506                                 b3(j) = 1;
    507                             }
    508                         }
    509                     }
    510                 }else if(c == 4){
    511                     if(z == 1){
    512                         for(j = i * i; j <= n; j += w + w){
    513                             b3(j) = 1;
    514                             j += w;
    515                             if(j <= n){
    516                                 b2(j) = 1;
    517                             }
    518                         }
    519                     }else if(z == 5){
    520                         for(j = i * i; j <= n; j += w){
    521                             b2(j) = 1;
    522                             j += w + w;
    523                             if(j <= n){
    524                                 b3(j) = 1;
    525                             }
    526                         }
    527                     }
    528                 }
    529             }
    530         }
    531         i += 2;
    532         if(i <= n && !b3(i))
    533         {
    534             Ans += cnt(i,n)*f(i);
    535             if(i <= 20000){
    536                 w = i + i;
    537                 c = w % 6;
    538                 z = (i * i) % 6;
    539                 if(c == 0){
    540                     if(z == 1){
    541                         for(j = i * i; j <= n; j += w){
    542                             b3(j) = 1;
    543                         }
    544                     }else if(z == 5){
    545                         for(j = i * i; j <= n; j += w){
    546                             b2(j) = 1;
    547                         }
    548                     }
    549                 }else if(c == 2){
    550                     if(z == 1){
    551                         for(j = i * i; j <= n; j += w){
    552                             b3(j) = 1;
    553                             j += w + w;
    554                             if(j <= n){
    555                                 b2(j) = 1;
    556                             }
    557                         }
    558                     }else if(z == 5){
    559                         for(j = i * i; j <= n; j += w + w){
    560                             b2(j) = 1;
    561                             j += w;
    562                             if(j <= n){
    563                                 b3(j) = 1;
    564                             }
    565                         }
    566                     }
    567                 }else if(c == 4){
    568                     if(z == 1){
    569                         for(j = i * i; j <= n; j += w + w){
    570                             b3(j) = 1;
    571                             j += w;
    572                             if(j <= n){
    573                                 b2(j) = 1;
    574                             }
    575                         }
    576                     }else if(z == 5){
    577                         for(j = i * i; j <= n; j += w){
    578                             b2(j) = 1;
    579                             j += w + w;
    580                             if(j <= n){
    581                                 b3(j) = 1;
    582                             }
    583                         }
    584                     }
    585                 }
    586             }
    587         }
    588     }
    589     printf("%u\n",Ans);
    590     return 0;
    591 }
    592 ```
    593 
    594 **Solution(000000)**
    595 
    596 ```
    597 #include <bits/stdc++.h>
    598 
    599 using namespace std;
    600 typedef unsigned int ll;
    601 const ll maxn=4e8;
    602 const ll maxp=sqrt(maxn)+10;
    603 ll f[4][maxp],g[4][maxp];
    604 ll n,m,A,B,C,D,ans,res,tmp,rt;
    605 
    606 ll p1(ll x){
    607     ll y=x+1; if (x%2==0) x/=2; else y/=2;
    608     return x*y;
    609 }
    610 ll p2(ll x){
    611     long long y=x+1,z=x*2+1;
    612     if (x%2==0) x/=2; else y/=2;
    613     if (z%3==0) z/=3; else if (x%3==0) x/=3; else y/=3;
    614     return (ll)x*y*z;
    615 }
    616 ll p3(ll x){
    617     ll y=p1(x);
    618     return y*y;
    619 }
    620 bool is_prime(ll x){
    621     for (ll i=2;i*i<=x;i++) if (x%i==0) return false;
    622     return true;
    623 }
    624 
    625 ll solve(ll n)
    626 {
    627     ll i,j,rt,o[4];
    628     for (m=1;m*m<=n;m++) {
    629         f[0][m]=(n/m-1);
    630         f[1][m]=(p1(n/m)-1)*C;
    631         f[2][m]=(p2(n/m)-1)*B;
    632         f[3][m]=(p3(n/m)-1)*A;
    633     }
    634     for (i=1;i<=m;i++) {
    635         g[0][i]=(i-1);
    636         g[1][i]=(p1(i)-1)*C;
    637         g[2][i]=(p2(i)-1)*B;
    638         g[3][i]=(p3(i)-1)*A;
    639     }
    640     for (i=2;i<=m;i++) {
    641         if (g[0][i]==g[0][i-1]) continue;
    642         o[0]=1; for (int w=1;w<4;w++) o[w]=o[w-1]*i;
    643         for (j=1;j<=min(m-1,n/i/i);j++)
    644             for (int w=0;w<4;w++)
    645                 if (i*j<m) f[w][j]-=o[w]*(f[w][i*j]-g[w][i-1]);
    646                 else f[w][j]-=o[w]*(g[w][n/i/j]-g[w][i-1]);
    647         for (j=m;j>=i*i;j--)
    648             for (int w=0;w<4;w++)
    649                 g[w][j]-=o[w]*(g[w][j/i]-g[w][i-1]);
    650     }
    651     for (int i=1;i<=m+1;i++) f[0][i]*=D,g[0][i]*=D;
    652     rt=0;
    653     for (ll i=1;n/i>m;i++) {
    654         for (int w=0;w<4;w++) rt+=(f[w][i]-g[w][m]);
    655         //cout<<"H"<<rt<<endl;
    656     }
    657     return rt;
    658 }
    659 
    660 int main()
    661 {
    662     //freopen("input.txt","r",stdin);
    663     ll n; cin >> n >> A >> B >> C >> D;
    664     ans=solve(n);
    665     for (ll i=2;i<=m;i++){
    666         if (is_prime(i)){
    667             res=A*i*i*i+B*i*i+C*i+D; tmp=n;
    668             while (tmp){
    669                 ans+=res*(tmp/i);
    670                 tmp/=i;
    671             }
    672         }
    673     }
    674     cout << ans << endl;
    675     return 0;
    676 }
    677 ```
    678 
    679 Tutorial is loading...
    680 
    681 **Solution(arsijo)**
    682 
    683 ```
    684 #include <bits/stdc++.h>
    685 using namespace std;
    686 
    687 const int MAX = 1e5 + 10;
    688 
    689 bool black[MAX]; // is it vertex black now
    690 vector<int> vec[MAX]; // main edges
    691 bool old_black[MAX]; // to remember the tree before block
    692 
    693 const int MAX_BLOCK_SIZE = 600;
    694 
    695 int t[MAX], v[MAX]; // queries
    696 
    697 bool used[MAX]; // is in mini-tree
    698 vector<pair<pair<int, int>, int> > v2[MAX]; // mini-tree edges (son, number of white vertices, dist)
    699 int push[MAX]; // push of the i-th vertex in mini-tree
    700 bool clear[MAX]; // do we need to clear first
    701 
    702 void dfs_1(int pos, int prev = -1, int white = 0, int dist = 0){
    703     if(used[pos]){
    704         if(prev != -1){
    705             v2[prev].push_back(make_pair(make_pair(pos, white), dist));
    706         }
    707         for(int a : vec[pos]){
    708             dfs_1(a, pos, 0, 0);
    709         }
    710     }else{
    711         if(!black[pos]){
    712             white++;
    713         }
    714         for(int a : vec[pos]){
    715             dfs_1(a, prev, white, dist + 1);
    716         }
    717     }
    718 }
    719 
    720 void make_1(int pos){
    721     if(!black[pos]){
    722         black[pos] = true;
    723         return;
    724     }
    725     push[pos]++;
    726     for(auto a : v2[pos]){
    727         if(a.first.second + 1 <= push[pos]){
    728             make_1(a.first.first);
    729         }
    730     }
    731 }
    732 
    733 void make_2(int pos){
    734     black[pos] = false;
    735     push[pos] = 0;
    736     clear[pos] = true;
    737     for(auto &a : v2[pos]){
    738         a.first.second = a.second;
    739         make_2(a.first.first);
    740     }
    741 }
    742 
    743 void dfs_2(int pos, int p = 0, bool cl = false){
    744     if(used[pos]){
    745         p = push[pos];
    746         cl |= clear[pos];
    747     }else{
    748         black[pos] = old_black[pos];
    749         if(cl){
    750             black[pos] = false;
    751         }
    752         if(!black[pos] && p){
    753             black[pos] = true;
    754             p--;
    755         }
    756     }
    757     for(int a : vec[pos]){
    758         dfs_2(a, p, cl);
    759     }
    760 }
    761 
    762 int main(){
    763     ios_base::sync_with_stdio();
    764     cin.tie(0);
    765     cout.tie(0);
    766     int n, q;
    767     cin >> n >> q;
    768     for(int i = 2; i <= n; i++){
    769         int a;
    770         cin >> a;
    771         vec[a].push_back(i);
    772     }
    773     for(int i = 1; i <= q; i++){
    774         cin >> t[i] >> v[i];
    775     }
    776     int root = 1;
    777     for(int i = 1; i <= q; i += MAX_BLOCK_SIZE){
    778         for(int j = 1; j <= n; j++){
    779             used[j] = false;
    780             v2[j].clear();
    781             old_black[j] = black[j];
    782             push[j] = 0;
    783             clear[j] = false;
    784         }
    785         for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){
    786             used[v[i + j]] = true;
    787         }
    788         dfs_1(root);
    789         for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){
    790             int t = ::t[i + j];
    791             int v = ::v[i + j];
    792             if(t == 1){
    793                 make_1(v);
    794             }else if(t == 2){
    795                 make_2(v);
    796             }else{
    797                 cout << (black[v] ? "black" : "white") << "\n";
    798             }
    799         }
    800         dfs_2(root);
    801     }
    802     return 0;
    803 }
    804 ```
    805 
    806 Tutorial is loading...
    807 
    808 **Solution(Magolor)**
    809 
    810 ```
    811 #include <bits/stdc++.h>
    812 using namespace std;
    813 #define MAXN 200000
    814 #define MOD 998244353
    815 #define rint register int
    816 inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
    817 int n, m, q, B, C, T, fac[MAXN+5], efac[MAXN+5], Ans[MAXN+5], A[MAXN+5], t[MAXN+5], c[MAXN+5];
    818 int mp[MAXN+5], rv[480], h[480][100032], _init[MAXN+5], d[105][100032]; bitset<100032> b[480];
    819 typedef pair<int,int> pii; pii S[MAXN+5]; struct QU{int u,l,r,k,i;}Q[MAXN+5];
    820 inline bool cmpi(const QU &a, const QU &b)
    821 {
    822 	return a.i<b.i;
    823 }
    824 inline bool cmpm(const QU &a, const QU &b)
    825 {
    826 	return a.u^b.u?a.u<b.u:a.u&1?a.r<b.r:a.r>b.r;
    827 }
    828 //fastpow
    829 inline int fxp(int s, int n=MOD-2){int a=1;for(;n;n&1?a=1ll*a*s%MOD:0,s=1ll*s*s%MOD,n>>=1);return a;}
    830 inline void Init(int k)
    831 {
    832 	if(_init[k]) return;
    833 	_init[k] = ++C;
    834 	int *D = d[C], s = 1ll*m*k%MOD;
    835 	D[0] = 1;
    836 	for(rint i = 1; i <= n; i++)
    837 		D[i] = 1ll*D[i-1]*(s+i)%MOD;
    838 }
    839 inline int dxp(int a, int b)
    840 {
    841 	return 1ll*fac[a]*efac[a-b]%MOD;
    842 }
    843 inline int DXP(int k, int l)
    844 {
    845 	return d[_init[k]][l];	
    846 }
    847 void insert(int x)
    848 {
    849 	--h[t[x]][c[x]++];
    850 	++h[t[x]][c[x]];
    851 	S[++T] = pii(t[x],c[x]);
    852 }
    853 void erase(int x)
    854 {
    855 	--h[t[x]][c[x]--];
    856 	++h[t[x]][c[x]];
    857 	S[++T] = pii(t[x],c[x]);
    858 }
    859 inline int calc(int k)
    860 {
    861 	int _ = T; T = 0;
    862 	for(rint i = 1; i <= _; i++)
    863 		if(!b[S[i].first][S[i].second]&&h[S[i].first][S[i].second])
    864 			S[++T] = S[i], b[S[i].first][S[i].second] = 1;
    865 	int Ans = 1;
    866 	for(rint i = 1; i <= T; i++)
    867 	{
    868 		b[S[i].first][S[i].second] = 0;
    869 		Ans = 1ll*Ans*fxp(dxp(rv[S[i].first]+k,S[i].second),h[S[i].first][S[i].second])%MOD;
    870 	}
    871 	return Ans;
    872 }
    873 int main()
    874 {
    875 	n = MAXN;
    876 	for(rint i = fac[0] = 1; i <= n; i++)
    877 		fac[i] = 1ll*i*fac[i-1]%MOD;
    878 	efac[n] = fxp(fac[n]);
    879 	for(rint i = n; i; i--)
    880 		efac[i-1] = 1ll*i*efac[i]%MOD;
    881 	n = rf();
    882 	m = rf();
    883 	q = rf();
    884 	B = n/sqrt(q*2/3)+1;
    885 	for(rint i = 1; i <= n; i++)
    886 		++t[A[i]=rf()];
    887 	for(rint i = 1, c = 0; i <= n; i++)
    888 		mp[t[A[i]]]?:rv[mp[t[A[i]]]=++c]=t[A[i]];
    889 	for(rint i = 1; i <= m; i++)
    890 		t[i] = mp[t[i]];
    891 	for(rint i = 1, l, r, k; i <= q; i++)
    892 	{
    893 		l = rf();
    894 		r = rf();
    895 		k = rf();
    896 		Init(k);
    897 		Q[i] = {~-l/B,l,r,k,i};
    898 	}
    899 	sort(Q+1,Q+q+1,cmpm);
    900 	for(rint i = 1; i <= n; i++)
    901 		++h[t[A[i]]][0];
    902 	for(rint i = 1, l = 1, r = 0; i <= q; i++)
    903 	{
    904 		for(; l > Q[i].l; insert(A[--l]));
    905 		for(; r < Q[i].r; insert(A[++r]));
    906 		for(; l < Q[i].l; erase(A[l++]));
    907 		for(; r > Q[i].r; erase(A[r--]));
    908 		Ans[Q[i].i] = calc(Q[i].k);
    909 	}
    910 	sort(Q+1,Q+q+1,cmpi);
    911 	for(rint i = 1; i <= q; i++)
    912 		printf("%d\n",1ll*DXP(Q[i].k,n-(Q[i].r-Q[i].l+1))*Ans[i]%MOD);
    913 	return 0;
    914 }
    915 ```
    916 
    917 **Solution(Kostroma)**
    918 
    919 ```
    920 #pragma comment(linker, "/STACK:512000000")
    921 #include <bits/stdc++.h>
    922 using namespace std;
    923 
    924 #define all(a) a.begin(), a.end()
    925 typedef long long li;
    926 typedef long double ld;
    927 void solve(__attribute__((unused)) bool);
    928 void precalc();
    929 clock_t start;
    930 #define FILENAME ""
    931 
    932 int main() {
    933 #ifdef AIM
    934     string s = FILENAME;
    935 //    assert(!s.empty());
    936     freopen("/home/alexandero/ClionProjects/cryptozoology/input.txt", "r", stdin);
    937   //freopen("/home/alexandero/ClionProjects/cryptozoology/output.txt", "w", stdout);
    938 #else
    939 //    freopen(FILENAME ".in", "r", stdin);
    940 //    freopen(FILENAME ".out", "w", stdout);
    941     //freopen("input.txt", "r", stdin);
    942     //freopen("output.txt", "w", stdout);
    943 #endif
    944     start = clock();
    945     int t = 1;
    946 #ifndef AIM
    947     cout.sync_with_stdio(0);
    948     cin.tie(0);
    949 #endif
    950   precalc();
    951     cout.precision(10);
    952     cout << fixed;
    953     //cin >> t;
    954     int testNum = 1;
    955     while (t--) {
    956         //cout << "Case #" << testNum++ << ": ";
    957         solve(true);
    958     }
    959     cout.flush();
    960 #ifdef AIM1
    961     while (true) {
    962       solve(false);
    963   }
    964 #endif
    965 
    966 #ifdef AIM
    967     cout.flush();
    968     auto end = clock();
    969 
    970     usleep(10000);
    971     print_stats(end - start);
    972     usleep(10000);
    973 #endif
    974 
    975     return 0;
    976 }
    977 
    978 template<typename T>
    979 T binpow(T q, T w, T mod) {
    980     if (!w)
    981         return 1 % mod;
    982     if (w & 1)
    983         return q * 1LL * binpow(q, w - 1, mod) % mod;
    984     return binpow(q * 1LL * q % mod, w / 2, mod);
    985 }
    986 
    987 template<typename T>
    988 T gcd(T q, T w) {
    989     while (w) {
    990         q %= w;
    991         swap(q, w);
    992     }
    993     return q;
    994 }
    995 template<typename T>
    996 T lcm(T q, T w) {
    997     return q / gcd(q, w) * w;
    998 }
    999 
   1000 template <typename T>
   1001 void make_unique(vector<T>& a) {
   1002     sort(all(a));
   1003     a.erase(unique(all(a)), a.end());
   1004 }
   1005 
   1006 template<typename T>
   1007 void relax_min(T& cur, T val) {
   1008     cur = min(cur, val);
   1009 }
   1010 
   1011 template<typename T>
   1012 void relax_max(T& cur, T val) {
   1013     cur = max(cur, val);
   1014 }
   1015 
   1016 void precalc() {
   1017 }
   1018 
   1019 #define int li
   1020 const int mod = 998244353;
   1021 
   1022 struct Query {
   1023   int l, r, id;
   1024 };
   1025 
   1026 vector<int> res;
   1027 vector<int> a;
   1028 int n;
   1029 
   1030 int TIMER = 0;
   1031 const int C = 200500;
   1032 int used[C];
   1033 int cur_cnt[C];
   1034 int rev[C];
   1035 map<int, vector<int>> down;
   1036 vector<int> init;
   1037 
   1038 void kill(vector<Query>& all_q, int block_size, int k) {
   1039   vector<vector<Query>> by_block(n / block_size + 1);
   1040   for (auto& cur_q : all_q) {
   1041     by_block[cur_q.l / block_size].push_back(cur_q);
   1042   }
   1043   for (int i = 0; i < by_block.size(); ++i) {
   1044     ++TIMER;
   1045     auto& q = by_block[i];
   1046     sort(all(q), [&] (const Query& o1, const Query& o2) {
   1047       return o1.r < o2.r;
   1048     });
   1049     int cur_l = min(n, (i + 1) * block_size);
   1050     int cur_r = cur_l;
   1051     int cur_prod = 1;
   1052 
   1053     auto add_item = [&] (int val) {
   1054       if (used[val] != TIMER) {
   1055         used[val] = TIMER;
   1056         cur_cnt[val] = 0;
   1057       }
   1058       int cur_k = k + init[val];
   1059       ++cur_cnt[val];
   1060         cur_prod = cur_prod * (cur_k - cur_cnt[val] + 1) % mod;
   1061     };
   1062     auto remove_item = [&] (int val) {
   1063       int cur_k = k + init[val];
   1064         cur_prod = cur_prod * rev[cur_k - cur_cnt[val] + 1] % mod;
   1065       --cur_cnt[val];
   1066     };
   1067 
   1068     for (auto& cur_q : q) {
   1069       while (cur_r < cur_q.r) {
   1070         add_item(a[cur_r++]);
   1071       }
   1072       while (cur_l > cur_q.l) {
   1073         add_item(a[--cur_l]);
   1074       }
   1075       while (cur_r > cur_q.r) {
   1076         remove_item(a[--cur_r]);
   1077       }
   1078       while (cur_l < cur_q.l) {
   1079         remove_item(a[cur_l++]);
   1080       }
   1081         res[cur_q.id] = cur_prod * down[k][n - cur_q.r + cur_q.l] % mod;
   1082     }
   1083   }
   1084 }
   1085 
   1086 void solve(__attribute__((unused)) bool read) {
   1087   for (int i = 1; i < C; ++i) {
   1088     rev[i] = binpow(i, mod - 2, mod);
   1089   }
   1090   int m, Q;
   1091   //read = false;
   1092   if (read) {
   1093     cin >> n >> m >> Q;
   1094   } else {
   1095     n = 50000;
   1096     m = 100000;
   1097     Q = 50000;
   1098   }
   1099   a.resize(n);
   1100   init.assign(m, 0);
   1101   for (int i = 0; i < n; ++i) {
   1102     if (read) {
   1103       cin >> a[i];
   1104       --a[i];
   1105     } else {
   1106       a[i] = rand() % m;
   1107     }
   1108     ++init[a[i]];
   1109   }
   1110   map<int, vector<Query>> q;
   1111   for (int i = 0; i < Q; ++i) {
   1112     int l, r, k;
   1113     if (read) {
   1114       cin >> l >> r >> k;
   1115     } else {
   1116       do {
   1117         l = rand() % n + 1;
   1118         r = rand() % n + 1;
   1119       } while (l > r);
   1120       k = rand() % 100;
   1121     }
   1122     --l;
   1123     q[k].push_back({l, r, i});
   1124     down[k] = vector<int>();
   1125   }
   1126   res.assign(Q, 0);
   1127   for (auto& item : down) {
   1128     int init_val = (item.first * m) % mod;
   1129     auto& vec = item.second;
   1130     vec.assign(n + 1, 1);
   1131     for (int i = 1; i < vec.size(); ++i) {
   1132       vec[i] = vec[i - 1] * (init_val + i) % mod;
   1133     }
   1134   }
   1135   for (auto& item : q) {
   1136     int k = item.first;
   1137     auto& cur_q = item.second;
   1138     int block_size = std::max((int)(n / sqrt((int)cur_q.size())), 1LL);
   1139     kill(cur_q, block_size, k);
   1140   }
   1141 
   1142   for (int i = 0; i < Q; ++i) {
   1143     cout << res[i] << "\n";
   1144   }
   1145 
   1146 }
   1147 ```
   1148 
   1149 ### Bonus Problem
   1150 
   1151 It is the previous D1E and its standard solution is hacked. Can you solve it?
   1152 
   1153 **Bonus problem**
   1154 
   1155 **Legend**
   1156 
   1157 How can the man in the high castle, Abendsen, escape so many times? Because he has a full plan of escaping —— with his films.
   1158 
   1159 The map of the cities can be described as a tree (i.e. connected graph with *n* vertices and *n* - 1 edges) rooted at node 1 —— where Abenden lives.
   1160 
   1161 When he starts his escaping, he plans **at most** *k* travels: one travel is a simple path between two (not necessarily different) vertices. So he goes from 1 to some vertex *v*1, and then goes from *v*1 to *v*2, and so on ...
   1162 
   1163 When he is visiting a vertex (even though he has visited this vertex before) he will get some films. But in some vertexes, he has to give some films. Note that Abendsen \textbf{can} have a negative amount of films. But after every travel, he **has to have a non-negative amount of films**. Note that when Abendsen is starting a new travel, **he is visiting the starting vertex too**. It sounds weird but it is a different world!
   1164 
   1165 At first, Abendsen does not have any films.
   1166 
   1167 He wants to maximize the number of the films he gets after the escape. So please help him find out the maximized films number he can get.
   1168 
   1169 **Input Format**
   1170 
   1171 The first line two contains two integers *n* and *k* (1 ≤ *n* ≤ 1000, 1 ≤ *k* ≤ 106) —— the number of vertices and the maximum number of travels allowed.
   1172 
   1173 The second line contains *n* integers *w*1, *w*2, ..., *w**n* (|*w**i*| ≤ 108) —— how many films will Abendsen get (or give if *w**i* is negative) if he visits the *i*-th vertex.
   1174 
   1175 Each of the next *n* - 1 lines contains two integers *u**i* and *v**i* (1 ≤ *u**i*, *v**i* ≤ *n*, *u**i* ≠ *v**i*) —— vertices connected by the *i*-th edge.
   1176 
   1177 It is guaranteed that the input data describes a correct tree.
   1178 
   1179 **Output Format**
   1180 
   1181 Print one integer, the maximum number of films he can get.