codeforces-scrape

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

757.md (40750B)


      1 Source: https://codeforces.com/blog/entry/49743
      2 
      3 ## [757A — Gotta Catch Em' All!](//www.codeforces.com/contest/757/problem/A)
      4 
      5 **Author:** [Baba](/profile/Baba "Candidate Master Baba")  
      6 **Testers:** [virus_1010](/profile/virus_1010 "Specialist virus_1010") [born2rule](/profile/born2rule "Specialist born2rule")
      7 
      8 **Expected complexity**: ![](https://espresso.codeforces.com/92de30bfabf583a2c3a88f74b1d279cf6e3b0abf.png)  
      9 **Main idea**: Maintain counts of required characters.
     10 
     11 Since we are allowed to permute the string in any order to find the maximum occurences of the string "Bulbasaur", we simply keep the count of the letters 'B', 'u', 'l', 'b', 'a', 's', 'r'. Now the string "Bulbasaur" contains 1 'B', 2'u', 1 'l', 2'a', 1 's', 1'r' and 1 'b', thus the answer to the problem is Min(count('B'), count('b'), count('s'), count('r'), count('l'), count('a')/2, count('u')/2). You can maintain the counts using an array.
     12 
     13 **Corner Cases:**  
     14 1. Neglecting 'B' and while calculating the answer considering count('b')/2.  
     15 2. Considering a letter more than once ( 'a' and 'u' ).
     16 
     17 **Tester's code:**
     18 
     19 ```
     20 #include <bits/stdc++.h>
     21 using namespace std;
     22 
     23 int main()
     24 {
     25   map<char, int> m;
     26   string s;
     27   cin>>s;
     28   for(auto x : s)
     29     m[x]++;
     30 
     31   int ans = m['B'];
     32   ans = min(ans, m['u']/2);
     33   ans = min(ans, m['a']/2);
     34   ans = min(ans, m['b']);
     35   ans = min(ans, m['s']);
     36   ans = min(ans, m['r']);
     37   ans = min(ans, m['l']);
     38   cout << ans << endl;
     39   return 0;
     40 }
     41 ```
     42 
     43 ## [757B — Bash's Big Day](//www.codeforces.com/contest/757/problem/B)
     44 
     45 **Author**: [architrai](/profile/architrai "Expert architrai")  
     46 **Testers**: [mprocks](/profile/mprocks "Expert mprocks"), [deepanshugarg](/profile/deepanshugarg "Expert deepanshugarg")
     47 
     48 **Expected complexity**: ![](https://espresso.codeforces.com/70300144f69607131fcaa17251baebc65b782581.png)  
     49 **Main idea**: Square-root factorization and keeping count of prime factors.
     50 
     51 The problem can be simplified to finding a group of Pokemons such that their strengths have a common factor other that 1. We can do this by marking just the prime factors, and the answer will be the maximum count of a prime factor occurring some number of times. The prime numbers of each number can be found out using pre-computed sieve or square-root factorization.
     52 
     53 Corner Cases : Since a Pokemon cannot fight with itself (as mentioned in the note), the minimum answer is 1. Thus, even in cases where every subset of the input has gcd equal to 1, the answer will be 1.
     54 
     55 **Tester's code:**
     56 
     57 ```
     58 #include<bits/stdc++.h>
     59 using namespace std;
     60 int N;
     61 unordered_map<int, int> factors;
     62 int main()
     63 {
     64 	ios_base::sync_with_stdio(false);
     65 	cin >> N;
     66 
     67 	while(N--)
     68 	{
     69 		int strength;
     70 		cin >> strength;
     71 
     72 		int root = sqrt(strength);
     73 		for(int i = 2; i <= root; i++)
     74 		{
     75 			if(strength%i == 0)
     76 				factors[i]++;
     77 
     78 			while(strength%i ==
     79 					0) strength
     80 				/= i;
     81 		}
     82 
     83 		if(strength > 1) factors[strength]++; 
     84 	}
     85 
     86 	int ans = 1;
     87 	for(auto it = factors.begin(); it != factors.end(); it++)
     88 	{
     89 		ans = max(ans, (*it).second);
     90 	}
     91 
     92 	cout << ans << endl;
     93 
     94 	return 0;
     95 }
     96 ```
     97 
     98 ## [757C — Felicity is Coming!](//www.codeforces.com/contest/757/problem/C)
     99 
    100 **Author:** [shivamkakkar](/profile/shivamkakkar "Candidate Master shivamkakkar")  
    101 **Testers:** [codelegend](/profile/codelegend "Candidate Master codelegend")
    102 
    103 **Expected complexity**: ![](https://espresso.codeforces.com/4ac5d99a78bc2a1504667e0a3435014dbef1a1e1.png)  
    104 **Main idea**: Divide pokemon types into equivalence classes based on their counts in each list.
    105 
    106 Consider a valid evolution plan *f*. Let *c*[*p*, *g*] be the number of times Pokemon *p* appears in gym *g*. If *f*(*p*) = *q* then ![](https://espresso.codeforces.com/7391ffeabdd395e9e0974ed9842754ea2116a5d2.png).
    107 
    108 Now consider a group of Pokemon *P* such that all of them occur equal number of times in each gym (i.e. for each ![](https://espresso.codeforces.com/f9165728cf9d10c7defd75ed1bd3130bda587239.png)). Any permutation of this group would be a valid bijection.
    109 
    110 Say we have groups *s*1, *s*2, *s*3, ..., then the answer would be |*s*1|! |*s*2|! |*s*3|! ...  *mod* 109 + 7.
    111 
    112 For implementing groups, we can use *vector* < *vector* < *int* >  >  and for *i*-th pokemon, add the index of the gym to *i*-th vector.
    113 
    114 Now we need to find which of these vectors are equal. If we have the sorted *vector* < *vector* < *int* >  > , we can find equal elements by iterating over it and comparing adjacent elements.
    115 
    116 Consider the merge step of merge sort. For a comparison between 2 vectors *v*1 and *v*2, we cover at least *min*(*v*1.*size*(), *v*2.*size*()) elements. Hence ![](https://espresso.codeforces.com/92de30bfabf583a2c3a88f74b1d279cf6e3b0abf.png) work is done at each level. There are ![](https://espresso.codeforces.com/708a3d27c56bf6f704906554077ca85f7452e0cd.png) levels.
    117 
    118 Bonus : Try proving the time complexity for quicksort as well.
    119 
    120 **Authors's code:**
    121 
    122 ```
    123 #include<bits/stdc++.h>
    124 
    125 using namespace std;
    126 
    127 typedef long long LL;
    128 
    129 #define PB push_back
    130 #define ALL(X) X.begin(), X.end()
    131 
    132 #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
    133 
    134 const int N = 1e6;
    135 const LL MOD = 1e9 + 7;
    136 LL fact[N+1];
    137 int main()
    138 {
    139     fast_io;
    140     fact[0] = fact[1] = 1;
    141     for(LL i=2;i<=N;i++)
    142         fact[i] = (fact[i-1]*i)%MOD;
    143     int n,m;
    144     cin >> n >> m;
    145     vector< vector<int> > x(m);
    146     for(int i=0;i<n;i++) {
    147         int s;
    148         cin >> s;
    149         for(int j=0;j<s;j++) {
    150             int t;
    151             cin >> t;
    152             x[t-1].PB(i);
    153         }
    154     }
    155     for(int i=0;i<m;i++)
    156         sort(ALL(x[i]));
    157     sort(ALL(x));
    158     LL ans = 1;
    159     LL sm = 1;
    160     for(int i=1;i<m;i++) {
    161         if(x[i]==x[i-1])
    162             sm++;
    163         else
    164             ans = (ans*fact[sm])%MOD, sm = 1;
    165     }
    166     ans = (ans*fact[sm])%MOD;
    167     cout << ans << endl;
    168     return 0;
    169 }
    170 ```
    171 
    172 ## [757D — Felicity's Big Secret Revealed](//www.codeforces.com/contest/757/problem/D)
    173 
    174 **Author:** [saatwik27](/profile/saatwik27 "Expert saatwik27")  
    175 **Testers:** [imamit](/profile/imamit "Candidate Master imamit"),[abhinavaggarwal](/profile/abhinavaggarwal "Expert abhinavaggarwal"),[Chipe1](/profile/Chipe1 "Candidate Master Chipe1")
    176 
    177 **Expected complexity**: ![](https://espresso.codeforces.com/ba0db2c27716e96ad4a91805a221b22b46457c59.png)  
    178 **Main idea**: DP with Bitmask.
    179 
    180 This problem can be solved using Dynamic Programming with bitmask.
    181 
    182 The important thing to note here is that the set of distinct numbers formed will be a maximum of 20 numbers, i.e. from 1 to 20, else it won't fit 75 bits(1*(1 bits) + 2*(2 bits) + 4*(3 bits) + 8*(4 bits) + 5*(5 bits) = 74 bits). So, we can use a bitmask to denote a set of numbers that are included in a set of cuts.
    183 
    184 Let's see a Top-Down approach to solve it :
    185 
    186 Lets define the function *f*(*i*, *mask*) as : *f*(*i*, *mask*) denotes the number of sets of valid cuts that can be obtained from the state *i*, *mask*. The state formation is defined below.
    187 
    188 Let *M* be the maximum number among the numbers in *mask*. *mask* denotes a set of numbers that have been generated using some number of cuts, all of them before *b**i*. Out of these cuts, the last cut has been placed just before *b**i*. Now, first we check if the set of cuts obtained from *mask* is valid or not(in order for a mask to be valid, mask == 2*X* - 1 where *X* denotes number of set bits in the mask) and increment the answer accordingly if the mask is valid. And then we also have the option of adding another cut. We can add the next cut just before *b**x* provided the number formed by "*b**i* *b**i* + 1...*b**x* - 1" <= 20. Set the corresponding bit for this number formed to 1 in the *mask* to obtain *newMask* and recursively find *f*(*x*, *newMask*).
    189 
    190 **Author's code:**
    191 
    192 ```
    193 // Saatwik Singh Nagpal
    194 
    195 #include <bits/stdc++.h>
    196 using namespace std;
    197 
    198 #define TRACE
    199 #ifdef TRACE
    200 #define TR(...) __f(#__VA_ARGS__, __VA_ARGS__)
    201 template <typename Arg1>
    202 void __f(const char* name, Arg1&& arg1){
    203   cerr << name << " : " << arg1 << std::endl;
    204 }
    205 template <typename Arg1, typename... Args>
    206 void __f(const char* names, Arg1&& arg1, Args&&... args){
    207   const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    208 }
    209 #else
    210 #define TR(...)
    211 #endif
    212 
    213 typedef long long                LL;
    214 typedef vector < int >           VI;
    215 typedef pair < int,int >         II;
    216 typedef vector < II >            VII;
    217 
    218 #define MOD                      1000000007
    219 #define EPS                      1e-12
    220 #define N                        200100
    221 #define PB                       push_back
    222 #define MP                       make_pair
    223 #define F                        first 
    224 #define S                        second
    225 #define ALL(v)                   v.begin(),v.end()
    226 #define SZ(a)                    (int)a.size()
    227 #define FILL(a,b)                memset(a,b,sizeof(a))
    228 #define SI(n)                    scanf("%d",&n)
    229 #define SLL(n)                   scanf("%lld",&n)
    230 #define PLLN(n)                  printf("%lld\n",n)
    231 #define PIN(n)                   printf("%d\n",n)
    232 #define REP(i,j,n)               for(LL i=j;i<n;i++)
    233 #define PER(i,j,n)               for(LL i=n-1;i>=j;i--)
    234 #define endl                     '\n'
    235 #define fast_io                  ios_base::sync_with_stdio(false);cin.tie(NULL)
    236 
    237 #define FILEIO(name) \
    238   freopen(name".in", "r", stdin); \
    239   freopen(name".out", "w", stdout);
    240  
    241 inline int mult(int a , int b) { LL x = a; x *= LL(b); if(x >= MOD) x %= MOD; return x; }
    242 inline int add(int a , int b) { return a + b >= MOD ? a + b - MOD : a + b; }
    243 inline int sub(int a , int b) { return a - b < 0 ? MOD - b + a : a - b; }
    244 LL powmod(LL a,LL b) { if(b==0)return 1; LL x=powmod(a,b/2); LL y=(x*x)%MOD; if(b%2) return (a*y)%MOD; return y%MOD; }
    245 
    246 int dp[1<<20][77];
    247 int b[77] , n;
    248 int go(int mask , int i) {
    249   int cnt = __builtin_popcount(mask);
    250   if(i == n) {
    251     if(cnt != 0 && (1<<cnt)-1 == mask)
    252       return 1;
    253     return 0;
    254   }
    255   if(dp[mask][i] != -1) return dp[mask][i];
    256 
    257   int ret = 0;
    258   if(b[i] == 0)
    259     ret = go(mask , i+1);
    260   else {
    261     int num = 0;
    262     int j = i;
    263     while(1) {
    264       num *= 2;
    265       num += b[j];
    266       if(num > 20) break;
    267       //if(!(mask & (1<<(num-1))))
    268       ret = add(ret , go(mask | (1<<(num-1)) , j+1));
    269       j ++;
    270       if(j == n) break;
    271     }
    272     if(cnt != 0 && mask == (1<<cnt)-1)
    273       ret ++;
    274   }
    275   return dp[mask][i] = ret;
    276 }
    277 
    278 int main() {
    279   FILL(dp,-1);
    280   cin >> n;
    281   string s; cin >> s;
    282   REP(i,0,n)
    283     b[i] = s[i] - '0';
    284   int ans = 0;
    285   REP(i,0,n)
    286     ans = add(ans , go(0,i));
    287   PIN(ans);
    288   return 0;
    289 }
    290 ```
    291 
    292 ## [757E — Bash Plays with Functions](//codeforces.com/contest/757/problem/E)
    293 
    294 **Author**: [satyam.pandey](/profile/satyam.pandey "Expert satyam.pandey")  
    295 **Testers**: [Superty](/profile/Superty "Candidate Master Superty"),[vmrajas](/profile/vmrajas "Candidate Master vmrajas")
    296 
    297 **Expected complexity**: ![](https://espresso.codeforces.com/29875d1e574dfca1018b1af09810aaba53448627.png)  
    298 **Main idea**: Multiplicative Functions.
    299 
    300 We can easily see that *f*0 = 2(*number* *of* *distinct* *prime* *factors* *of* *n*). We can also see that it is a **multiplicative function**.
    301 
    302 We can also simplify the definition of *f**r* + 1 as:
    303 
    304 ![](https://espresso.codeforces.com/559d58ce5129ae3bd43f40fa9e6f85f61d981f82.png)
    305 
    306 Since *f*0 is a multiplicative function, *f**r* + 1 is also a multiplicative function. (by property of multiplicative functions)
    307 
    308 For each query, factorize *n*.
    309 
    310 Now, since *f**r* is a multiplicative function, if *n* can be written as:
    311 
    312 *n* = *p*1*e*1*p*2*e*2 ... *p**q**e**q*
    313 
    314 Then *f**r*(*n*) can be computed as:
    315 
    316 *f**r*(*n*) = *f**r*(*p*1*e*1) * *f**r*(*p*2*e*2) * ... * *f**r*(*p**q**e**q*)
    317 
    318 Now observe that the value of *f**r*(*p**n*) is independent of *p*, as *f*0(*p**n*) = 2. It is dependent only on *n*. So we calculate *f**r*(2*x*) for all r and x using a simple *R* * 20 DP as follows:
    319 
    320 ![](https://espresso.codeforces.com/4dda28caee7dfa35e9f028fb406bd2fd096dfca1.png)
    321 
    322 And now we can quickly compute *f**r*(*n*) for each query as:
    323 
    324 *f**r*(*n*) = *dp*[*r*][*e*1] * *dp*[*r*][*e*2] * ... * *dp*[*r*][*e**q*]
    325 
    326 **Author's code:**
    327 
    328 ```
    329 //Kyokai no Kanata //
    330 //Written by Satyam Pandey//
    331 #include<bits/stdc++.h>
    332 
    333 using namespace std;
    334 
    335 typedef pair<int,int> II;
    336 typedef vector<II> VII;
    337 typedef vector<int> VI;
    338 typedef vector< VI > VVI;
    339 typedef long long int LL;
    340 
    341 #define PB push_back
    342 #define MP make_pair
    343 #define F first
    344 #define S second
    345 #define SZ(a) (int)(a.size())
    346 #define ALL(a) a.begin(),a.end()
    347 #define SET(a,b) memset(a,b,sizeof(a))
    348 
    349 #define si(n) scanf("%d",&n)
    350 #define dout(n) printf("%d\n",n)
    351 #define sll(n) scanf("%lld",&n)
    352 #define lldout(n) printf("%lld\n",n)
    353 #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
    354 #define TRACE
    355 
    356 #ifdef TRACE
    357 #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    358 template <typename Arg1>
    359 void __f(const char* name, Arg1&& arg1){
    360   cerr<<name<<" : "<<arg1<<endl;
    361 }
    362 template <typename Arg1, typename... Args>
    363 void __f(const char* names,Arg1&& arg1,Args&&... args){
    364   const char* comma=strchr(names+1,',');
    365   cerr.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1,args...);
    366 }
    367 #else
    368 #define trace(...)
    369 #endif
    370 float  inf=std::numeric_limits<double>::infinity();
    371 LL INF=std::numeric_limits<LL>::max();
    372 //FILE *fin = freopen("in","r",stdin);
    373 //FILE *fout = freopen("out","w",stdout);
    374 const int R=int(1e6)+5,P=25,N=R,mod = int(1e9)+7;
    375 int  F[R][P],LP[N];
    376 inline void seive(){
    377   LP[1]=1;
    378   for(int i=2;i<N;i++){
    379     if(!LP[i])
    380       for(int j=i;j<N;j+=i)
    381         LP[j]=i;      
    382   }
    383 }
    384 inline void precalc()
    385 {
    386   for(int i=0;i<R;i++) F[i][0] = 1; 
    387   for(int i=1;i<P;i++) F[0][i] = 2;
    388   for(int i=1;i<R;i++) 
    389    for(int j=1;j<P;j++)
    390      F[i][j] = (F[i][j-1] + F[i-1][j])%mod;
    391 }
    392 inline LL solve(int r,int n)
    393 {
    394   LL ans=1;
    395   while(n!=1)
    396   {
    397       int cnt=0,p=LP[n];
    398       while(n%p==0) n/=p,cnt++;
    399       ans=(ans*F[r][cnt])%mod;
    400   }
    401   return ans;
    402 }
    403 int main()
    404 {
    405   seive();precalc();
    406   int q;si(q);
    407   int r,n;
    408   while(q--)
    409   {
    410     si(r);si(n);
    411     lldout(solve(r,n));
    412   }
    413   return 0;
    414 }
    415 ```
    416 
    417 ## [757F — Team Rocket Rises Again](//www.codeforces.com/contest/757/problem/F)
    418 
    419 **Author**: [Baba](/profile/Baba "Candidate Master Baba")  
    420 **Testers**: [shubhamvijay](/profile/shubhamvijay "Expert shubhamvijay"), [tanmayc25](/profile/tanmayc25 "Expert tanmayc25"), [vmrajas](/profile/vmrajas "Candidate Master vmrajas")
    421 
    422 **Expected complexity**: ![](https://espresso.codeforces.com/0a9508c2f0ea3e5f14b7c606266bccb1d1002c31.png)  
    423 **Main idea**: Building Dominator tree on shortest path DAG.
    424 
    425 First of all, we run Dijkstra's shortest path algorithm from *s* as the source vertex and construct the shortest path DAG of the given graph. Note that in the shortest path DAG, the length of any path from *s* to any other node *x* is equal to the length of the shortest path from *s* to *x* in the given graph.
    426 
    427 Now, let us analyze what the function *f*(*s*, *x*) means. It will be equal to the number of nodes *u* such that every path from *s* to *u* passes through node *x* in the shortest path DAG, such that on removing node *x* from the DAG, there will be no path from *s* to *u*.
    428 
    429 In other words, we want to find the number of nodes *u* that are dominated by node *x* considering *s* as the sources vertex in the shortest path DAG. This can be calculated by building dominator tree of the shortest path DAG considering *s* as the source vertex.  
    430 A node *u* is said to dominate a node *w* wrt source vertex *s* if all the paths from *s* to *w* in the graph must pass through node *u*.  
    431 You can read more about dominator tree [here](https://tanujkhattar.wordpress.com/2016/01/11/dominator-tree-of-a-directed-graph/).
    432 
    433 Once the dominator tree is formed, the answer for any node *x* is equal to the number of nodes in the subtree of *x* in the tree formed.
    434 
    435 **Author's code:**
    436 
    437 ```
    438 //Tanuj Khattar
    439 #include<bits/stdc++.h>
    440  
    441 using namespace std;
    442  
    443 typedef pair<int,int>   II;
    444 typedef vector< II >      VII;
    445 typedef vector<int>     VI;
    446 typedef vector< VI >  VVI;
    447 typedef long long int   LL;
    448  
    449 #define PB push_back
    450 #define MP make_pair
    451 #define F first
    452 #define S second
    453 #define SZ(a) (int)(a.size())
    454 #define ALL(a) a.begin(),a.end()
    455 #define SET(a,b) memset(a,b,sizeof(a))
    456  
    457 #define si(n) scanf("%d",&n)
    458 #define dout(n) printf("%d\n",n)
    459 #define sll(n) scanf("%lld",&n)
    460 #define lldout(n) printf("%lld\n",n)
    461 #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
    462  
    463 #define TRACE
    464  
    465 #ifdef TRACE
    466 #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    467 template <typename Arg1>
    468 void __f(const char* name, Arg1&& arg1){
    469   cerr << name << " : " << arg1 << std::endl;
    470 }
    471 template <typename Arg1, typename... Args>
    472 void __f(const char* names, Arg1&& arg1, Args&&... args){
    473   const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    474 }
    475 #else
    476 #define trace(...)
    477 #endif
    478  
    479 //FILE *fin = freopen("in","r",stdin);
    480 //FILE *fout = freopen("out","w",stdout);
    481 const int N = int(1e5)+10;
    482 const int M = int(2e5)+10;
    483 const LL INF = LL(1e16);
    484 namespace Dominator{
    485   VI g[N],tree[N],rg[N],bucket[N];
    486   int sdom[N],par[N],dom[N],dsu[N],label[N];
    487   int arr[N],rev[N],T;//1-Based directed graph input
    488   int Find(int u,int x=0){
    489     if(u==dsu[u])return x?-1:u;
    490     int v = Find(dsu[u],x+1);
    491     if(v<0)return u;
    492     if(sdom[label[dsu[u]]]<sdom[label[u]])
    493       label[u] = label[dsu[u]];
    494     dsu[u] = v;
    495     return x?v:label[u];
    496   }
    497   void Union(int u,int v){ //Add an edge u-->v
    498     dsu[v]=u;   //yup,its correct :)
    499   }
    500   void dfs0(int u){
    501     T++;arr[u]=T;rev[T]=u;
    502     label[T]=T;sdom[T]=T;dsu[T]=T;
    503     for(int i=0;i<SZ(g[u]);i++){
    504       int w = g[u][i];
    505       if(!arr[w])dfs0(w),par[arr[w]]=arr[u];
    506       rg[arr[w]].PB(arr[u]);
    507     }
    508   }
    509   void dfs1(int u,int p,int sub[]){
    510     sub[u]=1;
    511     for(auto w:tree[u])
    512       if(w!=p)
    513         dfs1(w,u,sub),sub[u]+=sub[w];
    514   }
    515   void reset(int n){
    516     for(int i=1;i<=n;i++){
    517       g[i].clear();rg[i].clear();tree[i].clear();arr[i]=0;
    518     }
    519     T=0;
    520   }
    521   void addEdge(int u,int v){
    522     g[u].PB(v);
    523   }
    524   //Build Dominator tree(in main)
    525   void get(int n,int root,int sub[]){
    526     dfs0(root);n=T;
    527     for(int i=n;i>=1;i--){
    528       for(int j=0;j<SZ(rg[i]);j++)
    529         sdom[i] = min(sdom[i],sdom[Find(rg[i][j])]);
    530       if(i>1)bucket[sdom[i]].PB(i);
    531       for(int j=0;j<SZ(bucket[i]);j++){
    532         int w = bucket[i][j],v = Find(w);
    533         if(sdom[v]==sdom[w])dom[w]=sdom[w];
    534         else dom[w] = v;
    535       }if(i>1)Union(par[i],i);
    536     }
    537     for(int i=2;i<=n;i++){
    538       if(dom[i]!=sdom[i])dom[i]=dom[dom[i]];
    539       tree[rev[i]].PB(rev[dom[i]]);
    540       tree[rev[dom[i]]].PB(rev[i]);
    541     }
    542     dfs1(rev[1],rev[1],sub);
    543   }//done :) 
    544 }
    545 int n,m,s,vis[N],sub[N];
    546 VII g[N];VI P[N];
    547 LL d[N];
    548 int dijkstra(int root){
    549   for(int i=1;i<=n;i++)d[i]=INF,P[i].clear();
    550   Dominator::reset(n);d[root]=0;SET(vis,0);
    551   set<pair<LL,int>> S;S.insert({d[root],root});
    552   while(!S.empty()){
    553     int u = S.begin()->S;
    554     S.erase(S.begin());
    555     if(vis[u])continue;
    556     vis[u]=1;
    557     for(auto w:g[u])
    558       if(d[u] + w.S < d[w.F]){
    559         d[w.F] = d[u] + w.S;
    560         P[w.F].clear();P[w.F].PB(u);
    561         S.insert({d[w.F],w.F});
    562       }
    563       else if(d[u]+w.S==d[w.F])
    564         P[w.F].PB(u);
    565   }
    566   for(int i=1;i<=n;i++)
    567     for(auto j : P[i])
    568         Dominator::addEdge(j,i);
    569   Dominator::get(n,root,sub);
    570   int mx = 0;
    571   for(int i=1;i<=n;i++)
    572     if(i!=root)
    573       mx = max(mx,sub[i]);
    574   return mx;
    575 }
    576 int main()
    577 {
    578   si(n);si(m);si(s);
    579   for(int i=1;i<=m;i++){
    580     int u,v,w;
    581     si(u);si(v);si(w);
    582     g[u].PB({v,w});
    583     g[v].PB({u,w});
    584   }
    585   dout(dijkstra(s));
    586   return 0;
    587 }
    588 ```
    589 
    590 Another approach for forming dominator tree is by observing that the shortest path directed graph formed is a DAG i.e. acyclic. So suppose we process the nodes of the shortest path dag in topological order and have a dominator tree of all nodes from which we can reach *x* already formed. Now, for the node *x*, we look at all the parents *p* of *x* in the DAG, and compute their LCA in the dominator tree built till now. We can now attach the node *x* as a child of the LCA in the tree.  
    591 For more details on this approach you can look at [EvenImage](/profile/EvenImage "Legendary Grandmaster EvenImage")'s solution [here](//codeforces.com/contest/757/submission/23761400).
    592 
    593 ## [757G — Can Bash Save the Day?](//www.codeforces.com/contest/757/problem/G)
    594 
    595 **Author**: [Baba](/profile/Baba "Candidate Master Baba")  
    596 **Testers**: [Toshad](/profile/Toshad "Candidate Master Toshad"), [abhinavaggarwal](/profile/abhinavaggarwal "Expert abhinavaggarwal")
    597 
    598 **Expected complexity**: ![](https://espresso.codeforces.com/7fda66574bd3afaa0ffac0239bdc6aa27767472a.png)  
    599 **Main idea**: Making the Centroid Tree Persistent.
    600 
    601 ### Simpler Problem
    602 
    603 First let's try to solve a much simpler problem given as follows.
    604 
    605 **Question:** Given a weighted tree, initially all the nodes of the given tree are inactive. We need to support the following operations fast :  
    606 *Query* *v* : Report the sum of distances of all active nodes from node *v* in the given tree.  
    607 *Activate* *v* : Mark node *v* to be an active node.
    608 
    609 **Solution:** The above problem can be easily solved by a fairly standard technique called Centroid Decomposition. You can read more about [here](https://tanujkhattar.wordpress.com/2016/01/10/centroid-decomposition-of-a-tree/)
    610 
    611 ### Solution Idea
    612 
    613 * Each query of the form (*L* *R* *v*) can be divided into two queries of form (1 *R* *v*)  -  (1 *L* - 1 *v*). Hence it is sufficient if we can support the following query: (*i* *v*) : Report the answer to query (1 *i* *v*)
    614 * To answer a single query of the form (*i* *v*) we can think of it as what is the sum of distance of all active nodes from node *v*, if we consider the first *i* nodes to be active.
    615 * Hence initially if we can preprocess the tree such that we activate nodes from 1 to *n* and after each update, store a copy of the centroid tree, then for each query (*i* *v*) we can lookup the centroid tree corresponding to *i*, which would have the first *i* nodes activated, and query for node *v* in ![](https://espresso.codeforces.com/00751ba6240d79065248c3972c9514e59c5a7439.png) time by looking at it’s ancestors.
    616 * To store a copy of the centroid tree for each *i*, we need to make it persistent.
    617 
    618 ### Persistent Centroid Tree : Key Ideas
    619 
    620 * Important thing to note is that single update in the centroid tree affects only the ancestors of the node in the tree.
    621 * Since height of the centroid tree is ![](https://espresso.codeforces.com/00751ba6240d79065248c3972c9514e59c5a7439.png), each update affects only ![](https://espresso.codeforces.com/00751ba6240d79065248c3972c9514e59c5a7439.png) other nodes in the centroid tree.
    622 * The idea is very similar to that of a persistent segment tree **BUT** unlike segtree, here each node of the centroid tree can have arbitrarily many children and hence simply creating a new copy of the affected nodes would not work because linking them to the children of old copy would take ![](https://espresso.codeforces.com/4336e63decb889b78c1c568d91339bd0f13e0d27.png) for each affected node and this number could be as large as *N*, hence it could take ![](https://espresso.codeforces.com/53018dec784fdcf768655aa4d8b2a6deabf3c792.png) time in total !
    623 
    624 ### Binarizing the Input Tree
    625 
    626 * To overcome the issue, we convert the given tree *T* into an equivalent binary tree *T*' by adding extra dummy nodes such that degree of each node in the transformed tree *T*' is  <  = 3, and the number of dummy nodes added is bounded by ![](https://espresso.codeforces.com/53018dec784fdcf768655aa4d8b2a6deabf3c792.png).
    627 * The dummy nodes are added such that the structure of the tree is preserved and weights of the edges added are set to 0.
    628 * To do this, consider a node *x* with degree *d* > 3 and let *c*1, *c*2...*c**d* be it's adjacent nodes. Add a new node *y* and change the edges as follows :
    629   + Delete the edges (*x* - *c*3), (*x* - *c*4) ... (*x* - *c**d*) and add the edge (*x* - *y*) such that degree of node *x* reduces to 3 from *d*.
    630   + Add edges (*y* - *c*3), (*y* - *c*4) ... (*y* - *c**d*) such that degree of node *y* is *d* - 1. Recursively call the procedure on node *y*.
    631 * Since degree of node *y* is *d* - 1 instead of original degree *d* of node *x*, it can be proved that we need to add at most ![](https://espresso.codeforces.com/53018dec784fdcf768655aa4d8b2a6deabf3c792.png) new nodes before degree of each node in the tree is  <  = 3.
    632 
    633 ### Conclusion
    634 
    635 Hence we perform centroid decomposition of this transformed tree *T*'. The centroid tree formed would have the following properties.
    636 
    637 * The height of the centroid tree is ![](https://espresso.codeforces.com/00751ba6240d79065248c3972c9514e59c5a7439.png)
    638 * Each node in the centroid tree has  ≤ 3 children.
    639 
    640 Now we can easily make this tree persistent by path-copying approach.  
    641 To handle the updates,
    642 
    643 * **Way-1 :** Observe that swapping *A*[*i*] and *A*[*i* + 1] would affect only the *i*'*th* persistent centroid tree, which can be rebuilt from the tree of *i* - 1 by a single update query. In this approach, for each update we add ![](https://espresso.codeforces.com/00751ba6240d79065248c3972c9514e59c5a7439.png) new nodes. See author's code below for more details.
    644 * **Way-2 :** First we go down to the lca of *A*[*x*] and *A*[*x* + 1] in the *x*'th persistent tree, updating the values as we go. Now, let *c**l* be the child of lca which is an ancestor of *A*[*x*], and let *c**r* be the child which is an ancestor of *A*[*x* + 1]. Now, we replace *c**r* of *x*'th persistent tree with *c**r* of (*x* + 1)'th persistent tree. Similarly, we replace *c**l* of *x* + 1'th persistent tree with *c**l* of *x*'th persistent tree. So now *A*[*x* + 1] is active in *x*'th persistent tree and both *A*[*x*] and *A*[*x* + 1] are active in (*x* + 1)'th persistent tree.To deactivate *A*[*x*] in *x*'th persistent tree we replace *c**l* of *x*'th persistent tree with *c**l* of (*x* - 1)'th persistent tree. Hence in this approach we do not need to create new ![](https://espresso.codeforces.com/00751ba6240d79065248c3972c9514e59c5a7439.png) nodes for each update. See testers's code below for more details.
    645 
    646 **Author's code:**
    647 
    648 ```
    649 //Tanuj Khattar
    650 #include<bits/stdc++.h>
    651 
    652 using namespace std;
    653 
    654 typedef pair<int,int>   II;
    655 typedef vector< II >      VII;
    656 typedef vector<int>     VI;
    657 typedef vector< VI > 	VVI;
    658 typedef long long int 	LL;
    659 
    660 #define PB push_back
    661 #define MP make_pair
    662 #define F first
    663 #define S second
    664 #define SZ(a) (int)(a.size())
    665 #define ALL(a) a.begin(),a.end()
    666 #define SET(a,b) memset(a,b,sizeof(a))
    667 
    668 #define si(n) scanf("%d",&n)
    669 #define dout(n) printf("%d\n",n)
    670 #define sll(n) scanf("%lld",&n)
    671 #define lldout(n) printf("%lld\n",n)
    672 #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
    673 
    674 #define TRACE
    675 
    676 #ifdef TRACE
    677 #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    678 template <typename Arg1>
    679 void __f(const char* name, Arg1&& arg1){
    680   cerr << name << " : " << arg1 << std::endl;
    681 }
    682 template <typename Arg1, typename... Args>
    683 void __f(const char* names, Arg1&& arg1, Args&&... args){
    684   const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    685 }
    686 #else
    687 #define trace(...)
    688 #endif
    689 
    690 //FILE *fin = freopen("in","r",stdin);
    691 //FILE *fout = freopen("out","w",stdout);
    692 const int MAXN = int(2e5)+10;
    693 const int MAXQ = int(2e5)+10;
    694 const int N = 2*MAXN;
    695 const int M = 2*N;
    696 int A[N]; //the permutation given
    697 int last[N],prv[M],nxt[M],to[M],deg[N],W[M],root[N];
    698 namespace tree{
    699   int sz,edge,vis[N];
    700   void addEdge(int u,int v,int w = 0){
    701     prv[edge] = last[u];W[edge] = w;
    702     if(last[u]!=-1)nxt[last[u]] = edge;
    703     last[u] = edge;
    704     to[edge] = v;
    705     edge++;
    706   }
    707   void addEdge1(int u,int v,int e){
    708     prv[e] = last[u];nxt[e] = -1;
    709     if(last[u]!=-1)nxt[last[u]] = e;
    710     last[u] = e;
    711     to[e] = v;
    712   }
    713   void deleteEdge(int u,int e){
    714     if(nxt[e]!=-1)prv[nxt[e]] = prv[e];
    715     if(prv[e]!=-1)nxt[prv[e]] = nxt[e];
    716     if(last[u] == e) last[u] = prv[e];
    717   }
    718   void changeEdge(int u,int v,vector<int> edges){
    719     //assert(SZ(edges) == 3);assert(deg[u] > 3);
    720     sort(ALL(edges));reverse(ALL(edges));
    721     for(auto e : edges)
    722       deleteEdge(u,e);
    723     last[v] = last[u];
    724     last[u] = -1;
    725     for(auto e : edges)
    726       addEdge1(u,to[e],e);
    727   }
    728   void pre(){
    729     SET(last,-1);SET(nxt,-1);
    730     SET(prv,-1);SET(to,-1);
    731   }
    732   //binarize the give tree.should be called from a leaf node.
    733   void binarize(int u,int p,int edge){
    734     vis[u]=1;
    735     if(deg[u] > 3){
    736       addEdge(u,++sz);
    737       deg[sz] = deg[u] - 1;
    738       set<int> temp;temp.insert(edge^1);
    739       int e = last[u];
    740       while(SZ(temp) < 3){
    741         temp.insert(e);
    742         e = prv[e];
    743       }
    744       changeEdge(u,sz,vector<int>(temp.begin(),temp.end()));
    745       deg[u] = 3;
    746       addEdge(sz,u);
    747     }
    748     for(int e = last[u];e >= 0; e = prv[e]){
    749       if(!vis[to[e]])
    750         binarize(to[e],u,e);
    751       else to[e] = p;
    752     }
    753   }
    754 }
    755 namespace Centroid{
    756   const int LOGN = 19;
    757   const int MAXC = N + (MAXN + MAXQ)*LOGN;
    758   int sub[N],nn,done[M],C[MAXC][3],L[N],R[N],idx[N],len[N],T,cnt[MAXC],lvl,IDX[MAXC];
    759   LL sum[MAXC],cntbn[MAXC],dist[LOGN][N];
    760   void dfs1(int u,int p){
    761     sub[u]=1;nn++;
    762     for(int e = last[u];e >= 0; e = prv[e]){
    763       int w = to[e];
    764       if(w!=p && !done[e])
    765         dfs1(w,u),sub[u]+=sub[w];
    766     }
    767   }
    768   int dfs2(int u,int p){
    769     for(int e = last[u];e >= 0; e = prv[e]){
    770       if(done[e])continue;int w = to[e];
    771       if(w!=p && sub[w]>nn/2)
    772         return dfs2(w,u);
    773     }return u;
    774   }
    775   void dfs(int u,int p){
    776     for(int e = last[u];e >= 0; e = prv[e]){
    777       if(done[e] || to[e]==p)continue;
    778       dist[lvl][to[e]] = dist[lvl][u] + W[e];
    779       dfs(to[e],u);
    780     }
    781   }
    782   int decompose(int root,int p,int l = 0){
    783     nn=0;dfs1(root,root);
    784     root=dfs2(root,root);
    785     lvl = l;dfs(root,root);
    786     idx[root] = ++T;
    787     int id = idx[root];IDX[T] = T;
    788     L[id] = T;
    789     for(int e = last[root];e >= 0;e = prv[e]){
    790       if(done[e])continue;
    791       assert(!done[e^1]);
    792       done[e]=done[e^1]=1;
    793       int c = decompose(to[e],root,l+1);
    794       assert(len[id] < 3);
    795       C[id][len[id]++] = idx[c];
    796     }
    797     R[id] = T;
    798     return root;
    799   }
    800   int update(int x,int id,int lvl=0){
    801     int ID = ++T;
    802     cnt[ID] = cnt[id] + 1;
    803     sum[ID] = sum[id] + dist[lvl][x];
    804     IDX[ID] = IDX[id];
    805     for(int i=0;i<len[IDX[id]];i++)
    806       if(L[IDX[C[id][i]]] <= idx[x] && idx[x] <= R[IDX[C[id][i]]]){
    807         C[ID][i] = update(x,C[id][i],lvl+1);
    808         cntbn[C[ID][i]] = cntbn[C[id][i]] + dist[lvl][x];
    809       }
    810       else C[ID][i] = C[id][i];
    811     return ID;
    812   }
    813   LL query(int x,int id,int lvl=0){
    814     LL ret = sum[id];
    815     for(int i=0;i<len[IDX[id]];i++)
    816       if(L[IDX[C[id][i]]] <= idx[x] && idx[x] <= R[IDX[C[id][i]]])
    817         ret += query(x,C[id][i],lvl+1) - cntbn[C[id][i]] + (cnt[id] - cnt[C[id][i]])*dist[lvl][x];
    818     return ret;
    819   }
    820 }
    821 void binarize(int n){
    822   int root = -1;
    823   for(int i=1;i<=n;i++)
    824     if(deg[i] == 1)
    825       root = i;
    826   tree::binarize(root,root,-1);
    827 }
    828 int main()
    829 {
    830   tree::pre();
    831   int n,q;
    832   si(n);si(q);
    833   tree::sz = n;
    834   for(int i=1;i<=n;i++)si(A[i]);
    835   for(int i=1;i<n;i++){
    836     int u,v,w;
    837     si(u);si(v);si(w);
    838     tree::addEdge(u,v,w);
    839     tree::addEdge(v,u,w);
    840     deg[u]++;deg[v]++;
    841   }
    842   //binarize the given tree
    843   binarize(n);
    844   //build the centroid tree.
    845   Centroid::decompose(1,-1);
    846   root[0] = 1;
    847   //make it persistent and handle the queries.
    848   for(int i=1;i<=n;i++)
    849     root[i] = Centroid::update(A[i],root[i-1]);
    850   const int MOD = (1 << 30);
    851   LL ans = 0;
    852   while(q--){
    853     int t;si(t);
    854     if(t==1){
    855       int l,r,v;
    856       si(l);si(r);si(v);
    857       l = l ^ ans;
    858       r = r ^ ans;
    859       v = v ^ ans;
    860       ans = Centroid::query(v,root[r])-Centroid::query(v,root[l-1]);
    861       lldout(ans);
    862       ans = ans % MOD;
    863     }
    864     else{
    865       int x;si(x);x = x ^ ans;
    866       root[x] = Centroid::update(A[x+1],root[x-1]);
    867       swap(A[x],A[x+1]);
    868     }
    869   }
    870   return 0;
    871 }
    872 ```
    873 
    874 **Testers's code:**
    875 
    876 ```
    877 //Toshad Salwekar
    878 #include<bits/stdc++.h>
    879 #define f(i,a,n) for(int i=a;i<n;i++)
    880 #define S second
    881 #define F first
    882 #define Sc(n) scanf("%lld",&n)
    883 #define scc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
    884 #define sp(a) scanf("%lld %lld",&a.first,&a.second)
    885 #define pb push_back
    886 #define mp make_pair
    887 #define lb lower_bound
    888 #define ub upper_bound
    889 #define all(a) a.begin(),a.end()
    890 #define sc(n) scanf("%d",&n)
    891 #define It iterator
    892 #define SET(a,b) memset(a,b,sizeof(a))
    893 #define DRT()  int t; cin>>t; while(t--)
    894 // inbuilt functions
    895 // __gcd,  __builtin_ffs,     (returns least significant 1-bit, __builtin_ffsll(1)=1)
    896 // __builtin_clz,             (returns number of leading zeroes in 
    897 // __builtin_popcount,
    898 using namespace std;
    899 typedef long long LL;
    900 typedef pair<int,LL> PII;
    901 typedef vector<int> vi;
    902 #define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
    903 #define trv(s,it) for(auto it:s)
    904 #define TRACE
    905 
    906 #ifdef TRACE
    907 #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    908 template <typename Arg1>
    909 void __f(const char* name, Arg1&& arg1){
    910 	cerr << name << " : " << arg1 << std::endl;
    911 }
    912 template <typename Arg1, typename... Args>
    913 void __f(const char* names, Arg1&& arg1, Args&&... args){
    914 	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    915 }
    916 #else
    917 #define trace(...)
    918 #endif
    919 #define N 400005
    920 #define LOGN 20
    921 const int MAX = N*LOGN;
    922 const int MOD = (1<<30);
    923 int cn[N],nn,par[N],arr[N],centroid,C,tot,anc[N];
    924 LL dis[LOGN][N];
    925 vector<PII> tree[N];
    926 bool mark[N];	stack<int> st;
    927 struct node
    928 {	int id,cn,len; LL sum,psum;
    929 	node* child[4];
    930 }*pers[N];
    931 node BUFF[MAX];
    932 int buf_len;
    933 int dfs1(int i,int p)
    934 {	int r=1,mx=0,t;
    935 	for(auto it:tree[i])
    936 		if(it.F!=p && !mark[it.F])
    937 			r+=dfs1(it.F,i);
    938 	cn[i]=r;
    939 	return r;
    940 }
    941 int dfs2(int i,int p,int num)
    942 {	for(auto it:tree[i])
    943 		if(cn[it.F]>num/2 && !mark[it.F] && it.F!=p)
    944 			return dfs2(it.F,i,num);
    945 	return i;
    946 }
    947 void dfs(int i,int p,LL d)
    948 {	for(auto it:tree[i])
    949 		if(it.F!=p && !mark[it.F])
    950 			dfs(it.F,i,d+it.S);
    951 	dis[C][i]=d;
    952 }
    953 void dec(int root, node* p,int c)
    954 {	dfs1(root,root);
    955 	int cen=dfs2(root,root,cn[root]);		//cen is centroid of current subtree
    956 	C=c;
    957 	dfs(cen,cen,0LL);
    958 	mark[cen]=1;
    959 	node* tmp= BUFF + buf_len++;
    960 	tmp->id=cen;
    961 	tmp->cn=0;   tmp->len=0;
    962 	tmp->sum=0;		
    963 	if(p!=NULL)
    964 	{	p->child[p->len++]=tmp;
    965 		par[cen]=p->id;
    966 	}
    967 	else
    968 	{	pers[0]=tmp;				//This means cen is the centroid
    969 		centroid=cen;
    970 	}
    971 	for(auto it:tree[cen])
    972 		if(!mark[it.F])
    973 			dec(it.F,tmp,c+1);
    974 }
    975 node* persist(node* root, int i,int l)
    976 {	
    977 	node* tmp= BUFF + buf_len++;
    978 	tmp->id=root->id;
    979 	tmp->sum=root->sum + dis[l][i];
    980 	if(l)
    981 		tmp->psum=root->psum + dis[l-1][i];
    982 	tmp->cn=root->cn + 1;
    983 	tmp->len=0;
    984 	f(j,0,root->len)
    985 		if(!st.empty() && (root->child[j])->id==st.top())
    986 		{	st.pop();
    987 			tmp->child[tmp->len++]=persist(root->child[j],i,l+1);
    988 		}
    989 		else
    990 			tmp->child[tmp->len++]=root->child[j];
    991 	return tmp;
    992 }
    993 LL query(node* root, int i,int l)
    994 {	LL ans=0;
    995 	ans+=(root->cn)*dis[l][i]+root->sum;					// Add all nodes in range which are in subtree(in centroid tree) of current node
    996 	f(j,0,root->len)
    997 		if(!st.empty() && root->child[j]->id==st.top())
    998 		{	st.pop();
    999 			ans-=(root->child[j]->psum)+(root->child[j]->cn)*dis[l][i];			//Subtract all nodes which will be considered in the child(i.e., they are
   1000 			ans+=query(root->child[j],i,l+1);							// in same subtree as the query node).
   1001 		}
   1002 	return ans;
   1003 }
   1004 void binarise(unordered_map<int,LL> &add,int i,PII p,bool fl)
   1005 {     unordered_map<int,LL> tmp;
   1006 	mark[i]=1;
   1007 	if(fl)									// fl=1 for those nodes which were not in original tree
   1008 	{     add.erase(p.F);
   1009 		tree[i].pb(p);
   1010 		tree[i].pb(*(add.begin()));
   1011 		add.erase(add.begin());
   1012 		if(add.size()>1)							// Need to create more nodes
   1013 		{     tree[i].pb(mp(tot++,0LL));
   1014 			binarise(add,tot-1,mp(i,0LL),1);
   1015 		}
   1016 		else				
   1017 		{     tree[i].pb(*(add.begin()));
   1018 			binarise(tmp,tree[i][2].F,mp(i,tree[i][2].S),0);
   1019 		}
   1020 		binarise(tmp,tree[i][1].F,mp(i,tree[i][1].S),0);
   1021 	}
   1022 	else if(tree[i].size()>3)
   1023 	{     int t=0;bool fl=0;
   1024 		if(tree[i][t].F==p.F)
   1025 			t++;
   1026 		f(j,t,tree[i].size())
   1027 			if(mark[tree[i][j].F] && tree[i].size()==4)				// This means that tree[i][j].F is the parent in original tree
   1028 				fl=1;
   1029 		if(fl)											// Only has 
   1030 		{	f(j,0,tree[i].size())
   1031 				if(tree[i][j]!=p && !mark[tree[i][j].F])
   1032 					binarise(tmp,tree[i][j].F,mp(i,tree[i][j].S),0);
   1033 				else if(mark[tree[i][j].F])
   1034 					tree[i][j]=p;
   1035 			return;
   1036 		}
   1037 			if(mark[tree[i][t].F])
   1038 				t++;
   1039 			binarise(tmp,tree[i][t].F,mp(i,tree[i][t].S),0);				//t represents the child which will stay the child of this node.
   1040 			f(j,0,tree[i].size())
   1041 				if(j==t);
   1042 				else if(!mark[tree[i][j].F]	&& tree[i][j].F!=p.F)
   1043 					tmp.insert(tree[i][j]);
   1044 				else if(mark[tree[i][j].F])							//Replace original parent with new parent
   1045 					tree[i][j]=p;
   1046 			PII tm=tree[i][t];
   1047 			tree[i].clear();
   1048 			if(i!=1)											// 1 is root. For all others, add parent.
   1049 				tree[i].pb(p);  
   1050 			tree[i].pb(tm);				 
   1051 			tree[i].pb(mp(tot++,0LL));								// Add new extra node
   1052 			binarise(tmp,tot-1,mp(i,0LL),1);
   1053 	}
   1054 	else
   1055 		f(j,0,tree[i].size())
   1056 			if(tree[i][j]!=p && !mark[tree[i][j].F])
   1057 				binarise(tmp,tree[i][j].F,mp(i,tree[i][j].S),0);
   1058 			else if(mark[tree[i][j].F])							//Replace original with new parent
   1059 				tree[i][j]=p;
   1060 }
   1061 
   1062 int main()
   1063 {
   1064 	int n,q; LL a,b,c;
   1065 	cin>>n>>q;
   1066 	tot=n+1;
   1067 	f(i,1,n+1)
   1068 		sc(arr[i]);
   1069 	f(i,1,n)
   1070 	{	scc(a,b,c);
   1071 		tree[a].pb(mp(b,c));
   1072 		tree[b].pb(mp(a,c));
   1073 	}
   1074 	unordered_map<int,LL> stmp;
   1075 	binarise(stmp,1,mp(0,0LL),0);
   1076 	SET(mark,0);
   1077 	dec(1,NULL,0);
   1078 	f(i,1,n+1)
   1079 	{
   1080 		int p=arr[i];
   1081 		while(p!=centroid)					//push all nodes to be added in a stack
   1082 		{	st.push(p);	
   1083 			p=par[p];
   1084 		}
   1085 		pers[i]=persist(pers[i-1],arr[i],0);
   1086 	}
   1087 	LL an = 0;
   1088 	f(i,1,q+1)
   1089 	{	Sc(a);
   1090 		Sc(b);
   1091 		if(a==1)
   1092 		{	Sc(c); Sc(a);
   1093 		  b = b ^ an; c = c ^ an; a = a ^ an;
   1094 			int p=a;
   1095 			an=0;
   1096 			while(p!=centroid)				//push all nodes to be queried in a stack
   1097 			{	st.push(p);
   1098 				p=par[p];
   1099 			}
   1100 			an-=query(pers[b-1],a,0);
   1101 			p=a;
   1102 			while(p!=centroid)				//push all nodes to be queried in a stack
   1103 			{	st.push(p);
   1104 				p=par[p];
   1105 			}
   1106 			an+=query(pers[c],a,0);
   1107 			printf("%lld\n",an);
   1108 			an %= MOD;
   1109 		}
   1110 		else 
   1111 		{   b = b ^ an;
   1112 		    int p=arr[b],lca=centroid,h=centroid;
   1113 			while(p!=centroid)
   1114 			{     anc[p]=i;								//mark all ancestors of arr[b]
   1115 				p=par[p];
   1116 			}
   1117 			p=arr[b+1];
   1118 			while(p!=centroid)
   1119 			{     if(anc[p]==i)
   1120 				{     lca=p; break; }
   1121 				h=p;									// h is the highest ancestor of arr[b+1] which is not an ancestor of arr[b]
   1122 				p=par[p];
   1123 			}
   1124 			node *rt1=pers[b], *rt2=pers[b+1], *rt=pers[b-1];
   1125 			int l=0,k=-1;
   1126 			while(rt->id!=lca)							//traverse down to lca in all 3 centroid trees.
   1127 			{     rt1->sum -= dis[l][arr[b]] - dis[l][arr[b+1]];
   1128 				if(l) 
   1129 					rt1->psum -= dis[l-1][arr[b]] - dis[l-1][arr[b+1]];		
   1130 				l++;
   1131 				f(j,0,rt1->len)
   1132 					if(anc[rt1->child[j]->id]==i)
   1133 					{     rt1=rt1->child[j];
   1134 						break;
   1135 					}
   1136 				f(j,0,rt2->len)
   1137 					if(anc[rt2->child[j]->id]==i)
   1138 					{     rt2=rt2->child[j];
   1139 						break;
   1140 					}
   1141 				f(j,0,rt->len)
   1142 					if(anc[rt->child[j]->id]==i)
   1143 					{     rt=rt->child[j];
   1144 						break;
   1145 					}
   1146 			}
   1147 			rt1->sum-=dis[l][arr[b]]-dis[l][arr[b+1]];			//update lca too
   1148 			if(l) 
   1149 				rt1->psum-=dis[l-1][arr[b]]-dis[l-1][arr[b+1]];
   1150 
   1151 /*	 This is the swapping part. 
   1152  *	 b1child represents the child containing arr[b], 
   1153  *	 b2child represents the child containing arr[b+1] and 
   1154  *	 bchild represents the child containing arr[b] in persistent centroid tree of first b-1 elements
   1155  *	 The difference between b1child and bchild is that in b1child the ans due to arr[b] is considered, but it is not so in bchild. 
   1156  *	 Now we replace b1child with bchild and add b2child in pers[b], so that in pers[b], arr[b+1] is now active and not arr[b].
   1157  *																						*/
   1158 			node *b1child=NULL,*b2child=NULL,*bchild=NULL;
   1159 			f(j,0,rt->len)							//find bchild It may not exist if arr[b] = lca
   1160 				if(anc[rt->child[j]->id]==i)
   1161 					bchild=rt->child[j];
   1162 			f(j,0,rt1->len)
   1163 				if(anc[rt1->child[j]->id]==i)				//find b1child. It may not exist if arr[b] = lca
   1164 				{     b1child=rt1->child[j]; k=j; }
   1165 			int vv=0;
   1166 			if(b1child!=NULL)							// vv is used to handle the case where b1child = NULL
   1167 				vv=b1child->id;
   1168 			f(j,0,rt2->len)
   1169 				if(rt2->child[j]->id==h)				//find b2child. It may not exist if arr[b+1] = lca
   1170 					b2child=rt2->child[j];
   1171 				else if(rt2->child[j]->id==vv)			
   1172 					rt2->child[j]=b1child;
   1173 			if(k>=0)								//Again, check if b1child exists.
   1174 				rt1->child[k]=bchild;
   1175 			f(j,0,rt1->len)
   1176 				if(rt1->child[j]->id==h)
   1177 					rt1->child[j]=b2child;
   1178 			swap(arr[b],arr[b+1]);
   1179 		}
   1180 
   1181 	}
   1182 }
   1183 ```
   1184 
   1185 Hope you enjoyed the problemset! Any feedback is appreciated! :)