[757A — Gotta Catch Em' All!](http://www.codeforces.com/contest/757/problem/A)↵
------------------↵
**Author:** [user:tanujkhattar,2017-01-13] ↵
**Testers:** [user:r.arora,2017-01-13] [user:born2rule,2017-01-13] ↵
↵
**Expected complexity**: $\mathcal{O}(n)$ ↵
**Main idea**: Maintain counts of required characters. ↵
↵
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.↵
↵
**Corner Cases:** ↵
1. Neglecting 'B' and while calculating the answer considering count('b')/2. ↵
2. Considering a letter more than once ( 'a' and 'u' ). ↵
↵
<spoiler summary="Tester's code:"> ↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main()↵
{↵
map<char, int> m;↵
string s;↵
cin>>s;↵
for(auto x : s)↵
m[x]++;↵
↵
int ans = m['B'];↵
ans = min(ans, m['u']/2);↵
ans = min(ans, m['a']/2);↵
ans = min(ans, m['b']);↵
ans = min(ans, m['s']);↵
ans = min(ans, m['r']);↵
ans = min(ans, m['l']);↵
cout << ans << endl;↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[757B — Bash's Big Day ](http://www.codeforces.com/contest/757/problem/B)↵
------------------↵
**Author**: [user:architrai,2017-01-13] ↵
**Testers**: [user:mprocks,2017-01-13], [user:deepanshugarg,2017-01-13] ↵
↵
**Expected complexity**: $\mathcal{O}(n\sqrt{max(s_i)})$ ↵
**Main idea**: Square-root factorization and keeping count of prime factors.↵
↵
↵
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.↵
↵
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.↵
↵
<spoiler summary="Tester's code:">↵
~~~~~↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
int N;↵
unordered_map<int, int> factors;↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin >> N;↵
↵
while(N--)↵
{↵
int strength;↵
cin >> strength;↵
↵
int root = sqrt(strength);↵
for(int i = 2; i <= root; i++)↵
{↵
if(strength%i == 0)↵
factors[i]++;↵
↵
while(strength%i ==↵
0) strength↵
/= i;↵
}↵
↵
if(strength > 1) factors[strength]++; ↵
}↵
↵
int ans = 1;↵
for(auto it = factors.begin(); it != factors.end(); it++)↵
{↵
ans = max(ans, (*it).second);↵
}↵
↵
cout << ans << endl;↵
↵
return 0;↵
}↵
↵
↵
~~~~~↵
</spoiler>↵
↵
[757C — Felicity is Coming! ](http://www.codeforces.com/contest/757/problem/C)↵
------------------↵
**Author:** [user:shivamkakkar,2017-01-13] ↵
**Testers:** [user:codelegend,2017-01-13] ↵
↵
**Expected complexity**: $\mathcal{O}(n log n)$ ↵
**Main idea**: Divide pokemon types into equivalence classes based on their counts in each list. ↵
↵
↵
↵
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 $c[p, g_i] = c[q, g_i] \quad \forall i$.↵
↵
Now consider a group of Pokemon $P$ such that all of them occur equal number of times in each gym (i.e. for each $p, q \in P, \quad f[p_i, g_k] = f[p_j, g_k] \quad \forall k$). Any permutation of this group would be a valid bijection.↵
↵
Say we have groups $s_1, s_2, s_3, \ldots$, then the answer would be $|s_1|!\,|s_2|!\,|s_3|!\,\ldots \,mod\, 10^9+7$.↵
↵
For implementing groups, we can use $ vector < vector <int> > $ and for $i$-th pokemon, add the index of the gym to $i$-th vector.↵
↵
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.↵
↵
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 $\mathcal{O}(n)$ work is done at each level. There are $\mathcal{O}(log n)$ levels.↵
↵
Bonus : Try proving the time complexity for quicksort as well.↵
↵
↵
↵
<spoiler summary="Authors's code:">↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long LL;↵
↵
#define PB push_back↵
#define ALL(X) X.begin(), X.end()↵
↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
↵
const int N = 1e6;↵
const LL MOD = 1e9 + 7;↵
LL fact[N+1];↵
int main()↵
{↵
fast_io;↵
fact[0] = fact[1] = 1;↵
for(LL i=2;i<=N;i++)↵
fact[i] = (fact[i-1]*i)%MOD;↵
int n,m;↵
cin >> n >> m;↵
vector< vector<int> > x(m);↵
for(int i=0;i<n;i++) {↵
int s;↵
cin >> s;↵
for(int j=0;j<s;j++) {↵
int t;↵
cin >> t;↵
x[t-1].PB(i);↵
}↵
}↵
for(int i=0;i<m;i++)↵
sort(ALL(x[i]));↵
sort(ALL(x));↵
LL ans = 1;↵
LL sm = 1;↵
for(int i=1;i<m;i++) {↵
if(x[i]==x[i-1])↵
sm++;↵
else↵
ans = (ans*fact[sm])%MOD, sm = 1;↵
}↵
ans = (ans*fact[sm])%MOD;↵
cout << ans << endl;↵
return 0;↵
}↵
↵
↵
~~~~~↵
</spoiler>↵
↵
[757D — Felicity's Big Secret Revealed ](http://www.codeforces.com/contest/757/problem/D)↵
------------------↵
**Author:** [user:saatwik27,2017-01-13] ↵
**Testers:** [user:imamit,2017-01-13],[user:abhinavaggarwal,2017-01-13],[user:Chipe1,2017-01-13]↵
↵
This problem can be solved using Dynamic Programming with bitmask. ↵
↵
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. ↵
↵
Let's see a Top-Down approach to solve it : ↵
↵
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. ↵
↵
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)$. ↵
↵
<spoiler summary="Author's code:">↵
~~~~~↵
↵
// Saatwik Singh Nagpal↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define TRACE↵
#ifdef TRACE↵
#define TR(...) __f(#__VA_ARGS__, __VA_ARGS__)↵
template <typename Arg1>↵
void __f(const char* name, Arg1&& arg1){↵
cerr << name << " : " << arg1 << std::endl;↵
}↵
template <typename Arg1, typename... Args>↵
void __f(const char* names, Arg1&& arg1, Args&&... args){↵
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);↵
}↵
#else↵
#define TR(...)↵
#endif↵
↵
typedef long long LL;↵
typedef vector < int > VI;↵
typedef pair < int,int > II;↵
typedef vector < II > VII;↵
↵
#define MOD 1000000007↵
#define EPS 1e-12↵
#define N 200100↵
#define PB push_back↵
#define MP make_pair↵
#define F first ↵
#define S second↵
#define ALL(v) v.begin(),v.end()↵
#define SZ(a) (int)a.size()↵
#define FILL(a,b) memset(a,b,sizeof(a))↵
#define SI(n) scanf("%d",&n)↵
#define SLL(n) scanf("%lld",&n)↵
#define PLLN(n) printf("%lld\n",n)↵
#define PIN(n) printf("%d\n",n)↵
#define REP(i,j,n) for(LL i=j;i<n;i++)↵
#define PER(i,j,n) for(LL i=n-1;i>=j;i--)↵
#define endl '\n'↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
↵
#define FILEIO(name) \↵
freopen(name".in", "r", stdin); \↵
freopen(name".out", "w", stdout);↵
↵
inline int mult(int a , int b) { LL x = a; x *= LL(b); if(x >= MOD) x %= MOD; return x; }↵
inline int add(int a , int b) { return a + b >= MOD ? a + b - MOD : a + b; }↵
inline int sub(int a , int b) { return a - b < 0 ? MOD - b + a : a - b; }↵
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; }↵
↵
int dp[1<<20][77];↵
int b[77] , n;↵
int go(int mask , int i) {↵
int cnt = __builtin_popcount(mask);↵
if(i == n) {↵
if(cnt != 0 && (1<<cnt)-1 == mask)↵
return 1;↵
return 0;↵
}↵
if(dp[mask][i] != -1) return dp[mask][i];↵
↵
int ret = 0;↵
if(b[i] == 0)↵
ret = go(mask , i+1);↵
else {↵
int num = 0;↵
int j = i;↵
while(1) {↵
num *= 2;↵
num += b[j];↵
if(num > 20) break;↵
//if(!(mask & (1<<(num-1))))↵
ret = add(ret , go(mask | (1<<(num-1)) , j+1));↵
j ++;↵
if(j == n) break;↵
}↵
if(cnt != 0 && mask == (1<<cnt)-1)↵
ret ++;↵
}↵
return dp[mask][i] = ret;↵
}↵
↵
int main() {↵
FILL(dp,-1);↵
cin >> n;↵
string s; cin >> s;↵
REP(i,0,n)↵
b[i] = s[i] - '0';↵
int ans = 0;↵
REP(i,0,n)↵
ans = add(ans , go(0,i));↵
PIN(ans);↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[757E — Bash Plays with Functions ](codeforces.com/contest/757/problem/E)↵
------------------↵
**Author**: [user:satyam.pandey,2017-01-13] ↵
**Testers**: [user:Superty,2017-01-13],[user:vmrajas,2017-01-13] ↵
↵
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**.↵
↵
We can also simplify the definition of $f_{r+1}$ as: ↵
$$f_{r+1}(n) = \sum_{d\|n} f_r(d)$$↵
↵
Since $f_0$ is a multiplicative function, $f_{r+1}$ is also a multiplicative function. (by property of multiplicative functions)↵
↵
For each query, factorize $n$.↵
↵
Now, since $f_r$ is a multiplicative function, if $n$ can be written as:↵
$$n=p_1^{e_1}p_2^{e_2}\ \cdots p_q^{e_q}$$↵
↵
Then $f_r(n)$ can be computed as:↵
$$f_r(n) = f_r(p_1^{e_1})*f_r(p_2^{e_2})* \cdots * f_r(p_q^{e_q})$$↵
↵
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:↵
↵
$$dp[r][x] = \sum_{i=0}^{x} dp[r-1][i]$$↵
↵
And now we can quickly compute $f_r(n)$ for each query as:↵
↵
$$f_r(n) = dp[r][e_1]*dp[r][e_2]* \cdots * dp[r][e_q]$$↵
↵
<spoiler summary="Author's code:">↵
~~~~~↵
↵
//Kyokai no Kanata //↵
//Written by Satyam Pandey//↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef pair<int,int> II;↵
typedef vector<II> VII;↵
typedef vector<int> VI;↵
typedef vector< VI > VVI;↵
typedef long long int LL;↵
↵
#define PB push_back↵
#define MP make_pair↵
#define F first↵
#define S second↵
#define SZ(a) (int)(a.size())↵
#define ALL(a) a.begin(),a.end()↵
#define SET(a,b) memset(a,b,sizeof(a))↵
↵
#define si(n) scanf("%d",&n)↵
#define dout(n) printf("%d\n",n)↵
#define sll(n) scanf("%lld",&n)↵
#define lldout(n) printf("%lld\n",n)↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
#define TRACE↵
↵
#ifdef TRACE↵
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)↵
template <typename Arg1>↵
void __f(const char* name, Arg1&& arg1){↵
cerr<<name<<" : "<<arg1<<endl;↵
}↵
template <typename Arg1, typename... Args>↵
void __f(const char* names,Arg1&& arg1,Args&&... args){↵
const char* comma=strchr(names+1,',');↵
cerr.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1,args...);↵
}↵
#else↵
#define trace(...)↵
#endif↵
float inf=std::numeric_limits<double>::infinity();↵
LL INF=std::numeric_limits<LL>::max();↵
//FILE *fin = freopen("in","r",stdin);↵
//FILE *fout = freopen("out","w",stdout);↵
const int R=int(1e6)+5,P=25,N=R,mod = int(1e9)+7;↵
int F[R][P],LP[N];↵
inline void seive(){↵
LP[1]=1;↵
for(int i=2;i<N;i++){↵
if(!LP[i])↵
for(int j=i;j<N;j+=i)↵
LP[j]=i; ↵
}↵
}↵
inline void precalc()↵
{↵
for(int i=0;i<R;i++) F[i][0] = 1; ↵
for(int i=1;i<P;i++) F[0][i] = 2;↵
for(int i=1;i<R;i++) ↵
for(int j=1;j<P;j++)↵
F[i][j] = (F[i][j-1] + F[i-1][j])%mod;↵
}↵
inline LL solve(int r,int n)↵
{↵
LL ans=1;↵
while(n!=1)↵
{↵
int cnt=0,p=LP[n];↵
while(n%p==0) n/=p,cnt++;↵
ans=(ans*F[r][cnt])%mod;↵
}↵
return ans;↵
}↵
int main()↵
{↵
seive();precalc();↵
int q;si(q);↵
int r,n;↵
while(q--)↵
{↵
si(r);si(n);↵
lldout(solve(r,n));↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
[757F — Team Rocket Rises Again ](http://www.codeforces.com/contest/757/problem/F)↵
------------------↵
**Author**: [user:tanujkhattar,2017-01-13] ↵
**Testers**: [user:shubhamvijay,2017-01-13], [user:tanmayc25,2017-01-13], [user:vmrajas,2017-01-13] ↵
↵
**Expected complexity**: $\mathcal{O}((N+M) \cdot logN)$ ↵
**Main idea**: Building Dominator tree on shortest path DAG. ↵
↵
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. ↵
↵
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$. ↵
↵
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. ↵
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$. ↵
You can read more about dominator tree [here](https://tanujkhattar.wordpress.com/2016/01/11/dominator-tree-of-a-directed-graph/). ↵
↵
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. ↵
↵
↵
↵
↵
<spoiler summary="Author's code:">↵
~~~~~↵
//Tanuj Khattar↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef pair<int,int> II;↵
typedef vector< II > VII;↵
typedef vector<int> VI;↵
typedef vector< VI > VVI;↵
typedef long long int LL;↵
↵
#define PB push_back↵
#define MP make_pair↵
#define F first↵
#define S second↵
#define SZ(a) (int)(a.size())↵
#define ALL(a) a.begin(),a.end()↵
#define SET(a,b) memset(a,b,sizeof(a))↵
↵
#define si(n) scanf("%d",&n)↵
#define dout(n) printf("%d\n",n)↵
#define sll(n) scanf("%lld",&n)↵
#define lldout(n) printf("%lld\n",n)↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
↵
#define TRACE↵
↵
#ifdef TRACE↵
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)↵
template <typename Arg1>↵
void __f(const char* name, Arg1&& arg1){↵
cerr << name << " : " << arg1 << std::endl;↵
}↵
template <typename Arg1, typename... Args>↵
void __f(const char* names, Arg1&& arg1, Args&&... args){↵
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);↵
}↵
#else↵
#define trace(...)↵
#endif↵
↵
//FILE *fin = freopen("in","r",stdin);↵
//FILE *fout = freopen("out","w",stdout);↵
const int N = int(1e5)+10;↵
const int M = int(2e5)+10;↵
const LL INF = LL(1e16);↵
namespace Dominator{↵
VI g[N],tree[N],rg[N],bucket[N];↵
int sdom[N],par[N],dom[N],dsu[N],label[N];↵
int arr[N],rev[N],T;//1-Based directed graph input↵
int Find(int u,int x=0){↵
if(u==dsu[u])return x?-1:u;↵
int v = Find(dsu[u],x+1);↵
if(v<0)return u;↵
if(sdom[label[dsu[u]]]<sdom[label[u]])↵
label[u] = label[dsu[u]];↵
dsu[u] = v;↵
return x?v:label[u];↵
}↵
void Union(int u,int v){ //Add an edge u-->v↵
dsu[v]=u; //yup,its correct :)↵
}↵
void dfs0(int u){↵
T++;arr[u]=T;rev[T]=u;↵
label[T]=T;sdom[T]=T;dsu[T]=T;↵
for(int i=0;i<SZ(g[u]);i++){↵
int w = g[u][i];↵
if(!arr[w])dfs0(w),par[arr[w]]=arr[u];↵
rg[arr[w]].PB(arr[u]);↵
}↵
}↵
void dfs1(int u,int p,int sub[]){↵
sub[u]=1;↵
for(auto w:tree[u])↵
if(w!=p)↵
dfs1(w,u,sub),sub[u]+=sub[w];↵
}↵
void reset(int n){↵
for(int i=1;i<=n;i++){↵
g[i].clear();rg[i].clear();tree[i].clear();arr[i]=0;↵
}↵
T=0;↵
}↵
void addEdge(int u,int v){↵
g[u].PB(v);↵
}↵
//Build Dominator tree(in main)↵
void get(int n,int root,int sub[]){↵
dfs0(root);n=T;↵
for(int i=n;i>=1;i--){↵
for(int j=0;j<SZ(rg[i]);j++)↵
sdom[i] = min(sdom[i],sdom[Find(rg[i][j])]);↵
if(i>1)bucket[sdom[i]].PB(i);↵
for(int j=0;j<SZ(bucket[i]);j++){↵
int w = bucket[i][j],v = Find(w);↵
if(sdom[v]==sdom[w])dom[w]=sdom[w];↵
else dom[w] = v;↵
}if(i>1)Union(par[i],i);↵
}↵
for(int i=2;i<=n;i++){↵
if(dom[i]!=sdom[i])dom[i]=dom[dom[i]];↵
tree[rev[i]].PB(rev[dom[i]]);↵
tree[rev[dom[i]]].PB(rev[i]);↵
}↵
dfs1(rev[1],rev[1],sub);↵
}//done :) ↵
}↵
int n,m,s,vis[N],sub[N];↵
VII g[N];VI P[N];↵
LL d[N];↵
int dijkstra(int root){↵
for(int i=1;i<=n;i++)d[i]=INF,P[i].clear();↵
Dominator::reset(n);d[root]=0;SET(vis,0);↵
set<pair<LL,int>> S;S.insert({d[root],root});↵
while(!S.empty()){↵
int u = S.begin()->S;↵
S.erase(S.begin());↵
if(vis[u])continue;↵
vis[u]=1;↵
for(auto w:g[u])↵
if(d[u] + w.S < d[w.F]){↵
d[w.F] = d[u] + w.S;↵
P[w.F].clear();P[w.F].PB(u);↵
S.insert({d[w.F],w.F});↵
}↵
else if(d[u]+w.S==d[w.F])↵
P[w.F].PB(u);↵
}↵
for(int i=1;i<=n;i++)↵
for(auto j : P[i])↵
Dominator::addEdge(j,i);↵
Dominator::get(n,root,sub);↵
int mx = 0;↵
for(int i=1;i<=n;i++)↵
if(i!=root)↵
mx = max(mx,sub[i]);↵
return mx;↵
}↵
int main()↵
{↵
si(n);si(m);si(s);↵
for(int i=1;i<=m;i++){↵
int u,v,w;↵
si(u);si(v);si(w);↵
g[u].PB({v,w});↵
g[v].PB({u,w});↵
}↵
dout(dijkstra(s));↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
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. ↵
For more details on this approach you can look at [user:moejy0viiiiiv,2017-01-13]'s solution [here](http://codeforces.net/contest/757/submission/23761400). ↵
↵
[757G — Can Bash Save the Day? ](http://www.codeforces.com/contest/757/problem/G)↵
------------------↵
**Author**: [user:tanujkhattar,2017-01-13] ↵
**Testers**: [user:Toshad,2017-01-13], [user:abhinavaggarwal,2017-01-13] ↵
↵
**Expected complexity**: $\mathcal{O}((N+Q) \cdot logN)$ ↵
**Main idea**: Making the Centroid Tree Persistent. ↵
↵
### Simpler Problem↵
↵
First let's try to solve a much simpler problem given as follows. ↵
↵
**Question:** Given a weighted tree, initially all the nodes of the given tree are inactive. We need to support the following operations fast : ↵
$Query \ v$ : Report the sum of distances of all active nodes from node $v$ in the given tree. ↵
$Activate \ v$ : Mark node $v$ to be an active node. ↵
↵
**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/) ↵
↵
### Solution Idea ↵
↵
- 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)$ ↵
- 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. ↵
- 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 $\mathcal{O}(logN)$ time by looking at it’s ancestors. ↵
- To store a copy of the centroid tree for each $i$, we need to make it persistent. ↵
↵
### Persistent Centroid Tree : Key Ideas↵
↵
- Important thing to note is that single update in the centroid tree affects only the ancestors of the node in the tree. ↵
- Since height of the centroid tree is $\mathcal{O}(logN)$, each update affects only $\mathcal{O}(logN)$ other nodes in the centroid tree. ↵
- 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 $\mathcal{O}(number \ of \ children)$ for each affected node and this number could be as large as $N$, hence it could take $\mathcal{O}(N)$ time in total ! ↵
↵
### Binarizing the Input Tree↵
↵
- 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 $\mathcal{O}(N)$. ↵
- The dummy nodes are added such that the structure of the tree is preserved and weights of the edges added are set to $0$. ↵
- 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 : ↵
- 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$.↵
- 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$. ↵
- 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 $\mathcal{O}(N)$ new nodes before degree of each node in the tree is $<=3$. ↵
↵
### Conclusion↵
↵
Hence we perform centroid decomposition of this transformed tree $T'$. The centroid tree formed would have the following properties.↵
↵
- The height of the centroid tree is $\mathcal{O}(logN)$ ↵
- Each node in the centroid tree has $\leq 3$ children.↵
↵
Now we can easily make this tree persistent by path-copying approach. ↵
To handle the updates,↵
↵
- **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 $\mathcal{O}(logN)$ new nodes. See author's code below for more details. ↵
- **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 $\mathcal{O}(logN)$ nodes for each update. See testers's code below for more details. ↵
↵
↵
<spoiler summary="Author's code:">↵
~~~~~↵
//Tanuj Khattar↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef pair<int,int> II;↵
typedef vector< II > VII;↵
typedef vector<int> VI;↵
typedef vector< VI > VVI;↵
typedef long long int LL;↵
↵
#define PB push_back↵
#define MP make_pair↵
#define F first↵
#define S second↵
#define SZ(a) (int)(a.size())↵
#define ALL(a) a.begin(),a.end()↵
#define SET(a,b) memset(a,b,sizeof(a))↵
↵
#define si(n) scanf("%d",&n)↵
#define dout(n) printf("%d\n",n)↵
#define sll(n) scanf("%lld",&n)↵
#define lldout(n) printf("%lld\n",n)↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
↵
#define TRACE↵
↵
#ifdef TRACE↵
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)↵
template <typename Arg1>↵
void __f(const char* name, Arg1&& arg1){↵
cerr << name << " : " << arg1 << std::endl;↵
}↵
template <typename Arg1, typename... Args>↵
void __f(const char* names, Arg1&& arg1, Args&&... args){↵
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);↵
}↵
#else↵
#define trace(...)↵
#endif↵
↵
//FILE *fin = freopen("in","r",stdin);↵
//FILE *fout = freopen("out","w",stdout);↵
const int MAXN = int(2e5)+10;↵
const int MAXQ = int(2e5)+10;↵
const int N = 2*MAXN;↵
const int M = 2*N;↵
int A[N]; //the permutation given↵
int last[N],prv[M],nxt[M],to[M],deg[N],W[M],root[N];↵
namespace tree{↵
int sz,edge,vis[N];↵
void addEdge(int u,int v,int w = 0){↵
prv[edge] = last[u];W[edge] = w;↵
if(last[u]!=-1)nxt[last[u]] = edge;↵
last[u] = edge;↵
to[edge] = v;↵
edge++;↵
}↵
void addEdge1(int u,int v,int e){↵
prv[e] = last[u];nxt[e] = -1;↵
if(last[u]!=-1)nxt[last[u]] = e;↵
last[u] = e;↵
to[e] = v;↵
}↵
void deleteEdge(int u,int e){↵
if(nxt[e]!=-1)prv[nxt[e]] = prv[e];↵
if(prv[e]!=-1)nxt[prv[e]] = nxt[e];↵
if(last[u] == e) last[u] = prv[e];↵
}↵
void changeEdge(int u,int v,vector<int> edges){↵
//assert(SZ(edges) == 3);assert(deg[u] > 3);↵
sort(ALL(edges));reverse(ALL(edges));↵
for(auto e : edges)↵
deleteEdge(u,e);↵
last[v] = last[u];↵
last[u] = -1;↵
for(auto e : edges)↵
addEdge1(u,to[e],e);↵
}↵
void pre(){↵
SET(last,-1);SET(nxt,-1);↵
SET(prv,-1);SET(to,-1);↵
}↵
//binarize the give tree.should be called from a leaf node.↵
void binarize(int u,int p,int edge){↵
vis[u]=1;↵
if(deg[u] > 3){↵
addEdge(u,++sz);↵
deg[sz] = deg[u] - 1;↵
set<int> temp;temp.insert(edge^1);↵
int e = last[u];↵
while(SZ(temp) < 3){↵
temp.insert(e);↵
e = prv[e];↵
}↵
changeEdge(u,sz,vector<int>(temp.begin(),temp.end()));↵
deg[u] = 3;↵
addEdge(sz,u);↵
}↵
for(int e = last[u];e >= 0; e = prv[e]){↵
if(!vis[to[e]])↵
binarize(to[e],u,e);↵
else to[e] = p;↵
}↵
}↵
}↵
namespace Centroid{↵
const int LOGN = 19;↵
const int MAXC = N + (MAXN + MAXQ)*LOGN;↵
int sub[N],nn,done[M],C[MAXC][3],L[N],R[N],idx[N],len[N],T,cnt[MAXC],lvl,IDX[MAXC];↵
LL sum[MAXC],cntbn[MAXC],dist[LOGN][N];↵
void dfs1(int u,int p){↵
sub[u]=1;nn++;↵
for(int e = last[u];e >= 0; e = prv[e]){↵
int w = to[e];↵
if(w!=p && !done[e])↵
dfs1(w,u),sub[u]+=sub[w];↵
}↵
}↵
int dfs2(int u,int p){↵
for(int e = last[u];e >= 0; e = prv[e]){↵
if(done[e])continue;int w = to[e];↵
if(w!=p && sub[w]>nn/2)↵
return dfs2(w,u);↵
}return u;↵
}↵
void dfs(int u,int p){↵
for(int e = last[u];e >= 0; e = prv[e]){↵
if(done[e] || to[e]==p)continue;↵
dist[lvl][to[e]] = dist[lvl][u] + W[e];↵
dfs(to[e],u);↵
}↵
}↵
int decompose(int root,int p,int l = 0){↵
nn=0;dfs1(root,root);↵
root=dfs2(root,root);↵
lvl = l;dfs(root,root);↵
idx[root] = ++T;↵
int id = idx[root];IDX[T] = T;↵
L[id] = T;↵
for(int e = last[root];e >= 0;e = prv[e]){↵
if(done[e])continue;↵
assert(!done[e^1]);↵
done[e]=done[e^1]=1;↵
int c = decompose(to[e],root,l+1);↵
assert(len[id] < 3);↵
C[id][len[id]++] = idx[c];↵
}↵
R[id] = T;↵
return root;↵
}↵
int update(int x,int id,int lvl=0){↵
int ID = ++T;↵
cnt[ID] = cnt[id] + 1;↵
sum[ID] = sum[id] + dist[lvl][x];↵
IDX[ID] = IDX[id];↵
for(int i=0;i<len[IDX[id]];i++)↵
if(L[IDX[C[id][i]]] <= idx[x] && idx[x] <= R[IDX[C[id][i]]]){↵
C[ID][i] = update(x,C[id][i],lvl+1);↵
cntbn[C[ID][i]] = cntbn[C[id][i]] + dist[lvl][x];↵
}↵
else C[ID][i] = C[id][i];↵
return ID;↵
}↵
LL query(int x,int id,int lvl=0){↵
LL ret = sum[id];↵
for(int i=0;i<len[IDX[id]];i++)↵
if(L[IDX[C[id][i]]] <= idx[x] && idx[x] <= R[IDX[C[id][i]]])↵
ret += query(x,C[id][i],lvl+1) - cntbn[C[id][i]] + (cnt[id] - cnt[C[id][i]])*dist[lvl][x];↵
return ret;↵
}↵
}↵
void binarize(int n){↵
int root = -1;↵
for(int i=1;i<=n;i++)↵
if(deg[i] == 1)↵
root = i;↵
tree::binarize(root,root,-1);↵
}↵
int main()↵
{↵
tree::pre();↵
int n,q;↵
si(n);si(q);↵
tree::sz = n;↵
for(int i=1;i<=n;i++)si(A[i]);↵
for(int i=1;i<n;i++){↵
int u,v,w;↵
si(u);si(v);si(w);↵
tree::addEdge(u,v,w);↵
tree::addEdge(v,u,w);↵
deg[u]++;deg[v]++;↵
}↵
//binarize the given tree↵
binarize(n);↵
//build the centroid tree.↵
Centroid::decompose(1,-1);↵
root[0] = 1;↵
//make it persistent and handle the queries.↵
for(int i=1;i<=n;i++)↵
root[i] = Centroid::update(A[i],root[i-1]);↵
const int MOD = (1 << 30);↵
LL ans = 0;↵
while(q--){↵
int t;si(t);↵
if(t==1){↵
int l,r,v;↵
si(l);si(r);si(v);↵
l = l ^ ans;↵
r = r ^ ans;↵
v = v ^ ans;↵
ans = Centroid::query(v,root[r])-Centroid::query(v,root[l-1]);↵
lldout(ans);↵
ans = ans % MOD;↵
}↵
else{↵
int x;si(x);x = x ^ ans;↵
root[x] = Centroid::update(A[x+1],root[x-1]);↵
swap(A[x],A[x+1]);↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Testers's code:">↵
~~~~~↵
//Toshad Salwekar↵
#include<bits/stdc++.h>↵
#define f(i,a,n) for(int i=a;i<n;i++)↵
#define S second↵
#define F first↵
#define Sc(n) scanf("%lld",&n)↵
#define scc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)↵
#define sp(a) scanf("%lld %lld",&a.first,&a.second)↵
#define pb push_back↵
#define mp make_pair↵
#define lb lower_bound↵
#define ub upper_bound↵
#define all(a) a.begin(),a.end()↵
#define sc(n) scanf("%d",&n)↵
#define It iterator↵
#define SET(a,b) memset(a,b,sizeof(a))↵
#define DRT() int t; cin>>t; while(t--)↵
// inbuilt functions↵
// __gcd, __builtin_ffs, (returns least significant 1-bit, __builtin_ffsll(1)=1)↵
// __builtin_clz, (returns number of leading zeroes in ↵
// __builtin_popcount,↵
using namespace std;↵
typedef long long LL;↵
typedef pair<int,LL> PII;↵
typedef vector<int> vi;↵
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)↵
#define trv(s,it) for(auto it:s)↵
#define TRACE↵
↵
#ifdef TRACE↵
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)↵
template <typename Arg1>↵
void __f(const char* name, Arg1&& arg1){↵
cerr << name << " : " << arg1 << std::endl;↵
}↵
template <typename Arg1, typename... Args>↵
void __f(const char* names, Arg1&& arg1, Args&&... args){↵
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);↵
}↵
#else↵
#define trace(...)↵
#endif↵
#define N 400005↵
#define LOGN 20↵
const int MAX = N*LOGN;↵
const int MOD = (1<<30);↵
int cn[N],nn,par[N],arr[N],centroid,C,tot,anc[N];↵
LL dis[LOGN][N];↵
vector<PII> tree[N];↵
bool mark[N]; stack<int> st;↵
struct node↵
{ int id,cn,len; LL sum,psum;↵
node* child[4];↵
}*pers[N];↵
node BUFF[MAX];↵
int buf_len;↵
int dfs1(int i,int p)↵
{ int r=1,mx=0,t;↵
for(auto it:tree[i])↵
if(it.F!=p && !mark[it.F])↵
r+=dfs1(it.F,i);↵
cn[i]=r;↵
return r;↵
}↵
int dfs2(int i,int p,int num)↵
{ for(auto it:tree[i])↵
if(cn[it.F]>num/2 && !mark[it.F] && it.F!=p)↵
return dfs2(it.F,i,num);↵
return i;↵
}↵
void dfs(int i,int p,LL d)↵
{ for(auto it:tree[i])↵
if(it.F!=p && !mark[it.F])↵
dfs(it.F,i,d+it.S);↵
dis[C][i]=d;↵
}↵
void dec(int root, node* p,int c)↵
{ dfs1(root,root);↵
int cen=dfs2(root,root,cn[root]); //cen is centroid of current subtree↵
C=c;↵
dfs(cen,cen,0LL);↵
mark[cen]=1;↵
node* tmp= BUFF + buf_len++;↵
tmp->id=cen;↵
tmp->cn=0; tmp->len=0;↵
tmp->sum=0; ↵
if(p!=NULL)↵
{ p->child[p->len++]=tmp;↵
par[cen]=p->id;↵
}↵
else↵
{ pers[0]=tmp; //This means cen is the centroid↵
centroid=cen;↵
}↵
for(auto it:tree[cen])↵
if(!mark[it.F])↵
dec(it.F,tmp,c+1);↵
}↵
node* persist(node* root, int i,int l)↵
{ ↵
node* tmp= BUFF + buf_len++;↵
tmp->id=root->id;↵
tmp->sum=root->sum + dis[l][i];↵
if(l)↵
tmp->psum=root->psum + dis[l-1][i];↵
tmp->cn=root->cn + 1;↵
tmp->len=0;↵
f(j,0,root->len)↵
if(!st.empty() && (root->child[j])->id==st.top())↵
{ st.pop();↵
tmp->child[tmp->len++]=persist(root->child[j],i,l+1);↵
}↵
else↵
tmp->child[tmp->len++]=root->child[j];↵
return tmp;↵
}↵
LL query(node* root, int i,int l)↵
{ LL ans=0;↵
ans+=(root->cn)*dis[l][i]+root->sum; // Add all nodes in range which are in subtree(in centroid tree) of current node↵
f(j,0,root->len)↵
if(!st.empty() && root->child[j]->id==st.top())↵
{ st.pop();↵
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↵
ans+=query(root->child[j],i,l+1); // in same subtree as the query node).↵
}↵
return ans;↵
}↵
void binarise(unordered_map<int,LL> &add,int i,PII p,bool fl)↵
{ unordered_map<int,LL> tmp;↵
mark[i]=1;↵
if(fl) // fl=1 for those nodes which were not in original tree↵
{ add.erase(p.F);↵
tree[i].pb(p);↵
tree[i].pb(*(add.begin()));↵
add.erase(add.begin());↵
if(add.size()>1) // Need to create more nodes↵
{ tree[i].pb(mp(tot++,0LL));↵
binarise(add,tot-1,mp(i,0LL),1);↵
}↵
else ↵
{ tree[i].pb(*(add.begin()));↵
binarise(tmp,tree[i][2].F,mp(i,tree[i][2].S),0);↵
}↵
binarise(tmp,tree[i][1].F,mp(i,tree[i][1].S),0);↵
}↵
else if(tree[i].size()>3)↵
{ int t=0;bool fl=0;↵
if(tree[i][t].F==p.F)↵
t++;↵
f(j,t,tree[i].size())↵
if(mark[tree[i][j].F] && tree[i].size()==4) // This means that tree[i][j].F is the parent in original tree↵
fl=1;↵
if(fl) // Only has ↵
{ f(j,0,tree[i].size())↵
if(tree[i][j]!=p && !mark[tree[i][j].F])↵
binarise(tmp,tree[i][j].F,mp(i,tree[i][j].S),0);↵
else if(mark[tree[i][j].F])↵
tree[i][j]=p;↵
return;↵
}↵
if(mark[tree[i][t].F])↵
t++;↵
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.↵
f(j,0,tree[i].size())↵
if(j==t);↵
else if(!mark[tree[i][j].F] && tree[i][j].F!=p.F)↵
tmp.insert(tree[i][j]);↵
else if(mark[tree[i][j].F]) //Replace original parent with new parent↵
tree[i][j]=p;↵
PII tm=tree[i][t];↵
tree[i].clear();↵
if(i!=1) // 1 is root. For all others, add parent.↵
tree[i].pb(p); ↵
tree[i].pb(tm); ↵
tree[i].pb(mp(tot++,0LL)); // Add new extra node↵
binarise(tmp,tot-1,mp(i,0LL),1);↵
}↵
else↵
f(j,0,tree[i].size())↵
if(tree[i][j]!=p && !mark[tree[i][j].F])↵
binarise(tmp,tree[i][j].F,mp(i,tree[i][j].S),0);↵
else if(mark[tree[i][j].F]) //Replace original with new parent↵
tree[i][j]=p;↵
}↵
↵
int main()↵
{↵
int n,q; LL a,b,c;↵
cin>>n>>q;↵
tot=n+1;↵
f(i,1,n+1)↵
sc(arr[i]);↵
f(i,1,n)↵
{ scc(a,b,c);↵
tree[a].pb(mp(b,c));↵
tree[b].pb(mp(a,c));↵
}↵
unordered_map<int,LL> stmp;↵
binarise(stmp,1,mp(0,0LL),0);↵
SET(mark,0);↵
dec(1,NULL,0);↵
f(i,1,n+1)↵
{↵
int p=arr[i];↵
while(p!=centroid) //push all nodes to be added in a stack↵
{ st.push(p); ↵
p=par[p];↵
}↵
pers[i]=persist(pers[i-1],arr[i],0);↵
}↵
LL an = 0;↵
f(i,1,q+1)↵
{ Sc(a);↵
Sc(b);↵
if(a==1)↵
{ Sc(c); Sc(a);↵
b = b ^ an; c = c ^ an; a = a ^ an;↵
int p=a;↵
an=0;↵
while(p!=centroid) //push all nodes to be queried in a stack↵
{ st.push(p);↵
p=par[p];↵
}↵
an-=query(pers[b-1],a,0);↵
p=a;↵
while(p!=centroid) //push all nodes to be queried in a stack↵
{ st.push(p);↵
p=par[p];↵
}↵
an+=query(pers[c],a,0);↵
printf("%lld\n",an);↵
an %= MOD;↵
}↵
else ↵
{ b = b ^ an;↵
int p=arr[b],lca=centroid,h=centroid;↵
while(p!=centroid)↵
{ anc[p]=i; //mark all ancestors of arr[b]↵
p=par[p];↵
}↵
p=arr[b+1];↵
while(p!=centroid)↵
{ if(anc[p]==i)↵
{ lca=p; break; }↵
h=p; // h is the highest ancestor of arr[b+1] which is not an ancestor of arr[b]↵
p=par[p];↵
}↵
node *rt1=pers[b], *rt2=pers[b+1], *rt=pers[b-1];↵
int l=0,k=-1;↵
while(rt->id!=lca) //traverse down to lca in all 3 centroid trees.↵
{ rt1->sum -= dis[l][arr[b]] - dis[l][arr[b+1]];↵
if(l) ↵
rt1->psum -= dis[l-1][arr[b]] - dis[l-1][arr[b+1]]; ↵
l++;↵
f(j,0,rt1->len)↵
if(anc[rt1->child[j]->id]==i)↵
{ rt1=rt1->child[j];↵
break;↵
}↵
f(j,0,rt2->len)↵
if(anc[rt2->child[j]->id]==i)↵
{ rt2=rt2->child[j];↵
break;↵
}↵
f(j,0,rt->len)↵
if(anc[rt->child[j]->id]==i)↵
{ rt=rt->child[j];↵
break;↵
}↵
}↵
rt1->sum-=dis[l][arr[b]]-dis[l][arr[b+1]]; //update lca too↵
if(l) ↵
rt1->psum-=dis[l-1][arr[b]]-dis[l-1][arr[b+1]];↵
↵
/* This is the swapping part. ↵
* b1child represents the child containing arr[b], ↵
* b2child represents the child containing arr[b+1] and ↵
* bchild represents the child containing arr[b] in persistent centroid tree of first b-1 elements↵
* 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. ↵
* 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].↵
* */↵
node *b1child=NULL,*b2child=NULL,*bchild=NULL;↵
f(j,0,rt->len) //find bchild It may not exist if arr[b] = lca↵
if(anc[rt->child[j]->id]==i)↵
bchild=rt->child[j];↵
f(j,0,rt1->len)↵
if(anc[rt1->child[j]->id]==i) //find b1child. It may not exist if arr[b] = lca↵
{ b1child=rt1->child[j]; k=j; }↵
int vv=0;↵
if(b1child!=NULL) // vv is used to handle the case where b1child = NULL↵
vv=b1child->id;↵
f(j,0,rt2->len)↵
if(rt2->child[j]->id==h) //find b2child. It may not exist if arr[b+1] = lca↵
b2child=rt2->child[j];↵
else if(rt2->child[j]->id==vv) ↵
rt2->child[j]=b1child;↵
if(k>=0) //Again, check if b1child exists.↵
rt1->child[k]=bchild;↵
f(j,0,rt1->len)↵
if(rt1->child[j]->id==h)↵
rt1->child[j]=b2child;↵
swap(arr[b],arr[b+1]);↵
}↵
↵
}↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Hope you enjoyed the problemset! Any feedback is appreciatd! :) ↵
------------------↵
**Author:** [user:tanujkhattar,2017-01-13] ↵
**Testers:** [user:r.arora,2017-01-13] [user:born2rule,2017-01-13] ↵
↵
**Expected complexity**: $\mathcal{O}(n)$ ↵
**Main idea**: Maintain counts of required characters. ↵
↵
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.↵
↵
**Corner Cases:** ↵
1. Neglecting 'B' and while calculating the answer considering count('b')/2. ↵
2. Considering a letter more than once ( 'a' and 'u' ). ↵
↵
<spoiler summary="Tester's code:"> ↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main()↵
{↵
map<char, int> m;↵
string s;↵
cin>>s;↵
for(auto x : s)↵
m[x]++;↵
↵
int ans = m['B'];↵
ans = min(ans, m['u']/2);↵
ans = min(ans, m['a']/2);↵
ans = min(ans, m['b']);↵
ans = min(ans, m['s']);↵
ans = min(ans, m['r']);↵
ans = min(ans, m['l']);↵
cout << ans << endl;↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[757B — Bash's Big Day ](http://www.codeforces.com/contest/757/problem/B)↵
------------------↵
**Author**: [user:architrai,2017-01-13] ↵
**Testers**: [user:mprocks,2017-01-13], [user:deepanshugarg,2017-01-13] ↵
↵
**Expected complexity**: $\mathcal{O}(n\sqrt{max(s_i)})$ ↵
**Main idea**: Square-root factorization and keeping count of prime factors.↵
↵
↵
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.↵
↵
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.↵
↵
<spoiler summary="Tester's code:">↵
~~~~~↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
int N;↵
unordered_map<int, int> factors;↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin >> N;↵
↵
while(N--)↵
{↵
int strength;↵
cin >> strength;↵
↵
int root = sqrt(strength);↵
for(int i = 2; i <= root; i++)↵
{↵
if(strength%i == 0)↵
factors[i]++;↵
↵
while(strength%i ==↵
0) strength↵
/= i;↵
}↵
↵
if(strength > 1) factors[strength]++; ↵
}↵
↵
int ans = 1;↵
for(auto it = factors.begin(); it != factors.end(); it++)↵
{↵
ans = max(ans, (*it).second);↵
}↵
↵
cout << ans << endl;↵
↵
return 0;↵
}↵
↵
↵
~~~~~↵
</spoiler>↵
↵
[757C — Felicity is Coming! ](http://www.codeforces.com/contest/757/problem/C)↵
------------------↵
**Author:** [user:shivamkakkar,2017-01-13] ↵
**Testers:** [user:codelegend,2017-01-13] ↵
↵
**Expected complexity**: $\mathcal{O}(n log n)$ ↵
**Main idea**: Divide pokemon types into equivalence classes based on their counts in each list. ↵
↵
↵
↵
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 $c[p, g_i] = c[q, g_i] \quad \forall i$.↵
↵
Now consider a group of Pokemon $P$ such that all of them occur equal number of times in each gym (i.e. for each $p, q \in P, \quad f[p_i, g_k] = f[p_j, g_k] \quad \forall k$). Any permutation of this group would be a valid bijection.↵
↵
Say we have groups $s_1, s_2, s_3, \ldots$, then the answer would be $|s_1|!\,|s_2|!\,|s_3|!\,\ldots \,mod\, 10^9+7$.↵
↵
For implementing groups, we can use $ vector < vector <int> > $ and for $i$-th pokemon, add the index of the gym to $i$-th vector.↵
↵
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.↵
↵
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 $\mathcal{O}(n)$ work is done at each level. There are $\mathcal{O}(log n)$ levels.↵
↵
Bonus : Try proving the time complexity for quicksort as well.↵
↵
↵
↵
<spoiler summary="Authors's code:">↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long LL;↵
↵
#define PB push_back↵
#define ALL(X) X.begin(), X.end()↵
↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
↵
const int N = 1e6;↵
const LL MOD = 1e9 + 7;↵
LL fact[N+1];↵
int main()↵
{↵
fast_io;↵
fact[0] = fact[1] = 1;↵
for(LL i=2;i<=N;i++)↵
fact[i] = (fact[i-1]*i)%MOD;↵
int n,m;↵
cin >> n >> m;↵
vector< vector<int> > x(m);↵
for(int i=0;i<n;i++) {↵
int s;↵
cin >> s;↵
for(int j=0;j<s;j++) {↵
int t;↵
cin >> t;↵
x[t-1].PB(i);↵
}↵
}↵
for(int i=0;i<m;i++)↵
sort(ALL(x[i]));↵
sort(ALL(x));↵
LL ans = 1;↵
LL sm = 1;↵
for(int i=1;i<m;i++) {↵
if(x[i]==x[i-1])↵
sm++;↵
else↵
ans = (ans*fact[sm])%MOD, sm = 1;↵
}↵
ans = (ans*fact[sm])%MOD;↵
cout << ans << endl;↵
return 0;↵
}↵
↵
↵
~~~~~↵
</spoiler>↵
↵
[757D — Felicity's Big Secret Revealed ](http://www.codeforces.com/contest/757/problem/D)↵
------------------↵
**Author:** [user:saatwik27,2017-01-13] ↵
**Testers:** [user:imamit,2017-01-13],[user:abhinavaggarwal,2017-01-13],[user:Chipe1,2017-01-13]↵
↵
This problem can be solved using Dynamic Programming with bitmask. ↵
↵
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. ↵
↵
Let's see a Top-Down approach to solve it : ↵
↵
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. ↵
↵
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)$. ↵
↵
<spoiler summary="Author's code:">↵
~~~~~↵
↵
// Saatwik Singh Nagpal↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define TRACE↵
#ifdef TRACE↵
#define TR(...) __f(#__VA_ARGS__, __VA_ARGS__)↵
template <typename Arg1>↵
void __f(const char* name, Arg1&& arg1){↵
cerr << name << " : " << arg1 << std::endl;↵
}↵
template <typename Arg1, typename... Args>↵
void __f(const char* names, Arg1&& arg1, Args&&... args){↵
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);↵
}↵
#else↵
#define TR(...)↵
#endif↵
↵
typedef long long LL;↵
typedef vector < int > VI;↵
typedef pair < int,int > II;↵
typedef vector < II > VII;↵
↵
#define MOD 1000000007↵
#define EPS 1e-12↵
#define N 200100↵
#define PB push_back↵
#define MP make_pair↵
#define F first ↵
#define S second↵
#define ALL(v) v.begin(),v.end()↵
#define SZ(a) (int)a.size()↵
#define FILL(a,b) memset(a,b,sizeof(a))↵
#define SI(n) scanf("%d",&n)↵
#define SLL(n) scanf("%lld",&n)↵
#define PLLN(n) printf("%lld\n",n)↵
#define PIN(n) printf("%d\n",n)↵
#define REP(i,j,n) for(LL i=j;i<n;i++)↵
#define PER(i,j,n) for(LL i=n-1;i>=j;i--)↵
#define endl '\n'↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
↵
#define FILEIO(name) \↵
freopen(name".in", "r", stdin); \↵
freopen(name".out", "w", stdout);↵
↵
inline int mult(int a , int b) { LL x = a; x *= LL(b); if(x >= MOD) x %= MOD; return x; }↵
inline int add(int a , int b) { return a + b >= MOD ? a + b - MOD : a + b; }↵
inline int sub(int a , int b) { return a - b < 0 ? MOD - b + a : a - b; }↵
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; }↵
↵
int dp[1<<20][77];↵
int b[77] , n;↵
int go(int mask , int i) {↵
int cnt = __builtin_popcount(mask);↵
if(i == n) {↵
if(cnt != 0 && (1<<cnt)-1 == mask)↵
return 1;↵
return 0;↵
}↵
if(dp[mask][i] != -1) return dp[mask][i];↵
↵
int ret = 0;↵
if(b[i] == 0)↵
ret = go(mask , i+1);↵
else {↵
int num = 0;↵
int j = i;↵
while(1) {↵
num *= 2;↵
num += b[j];↵
if(num > 20) break;↵
//if(!(mask & (1<<(num-1))))↵
ret = add(ret , go(mask | (1<<(num-1)) , j+1));↵
j ++;↵
if(j == n) break;↵
}↵
if(cnt != 0 && mask == (1<<cnt)-1)↵
ret ++;↵
}↵
return dp[mask][i] = ret;↵
}↵
↵
int main() {↵
FILL(dp,-1);↵
cin >> n;↵
string s; cin >> s;↵
REP(i,0,n)↵
b[i] = s[i] - '0';↵
int ans = 0;↵
REP(i,0,n)↵
ans = add(ans , go(0,i));↵
PIN(ans);↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
[757E — Bash Plays with Functions ](codeforces.com/contest/757/problem/E)↵
------------------↵
**Author**: [user:satyam.pandey,2017-01-13] ↵
**Testers**: [user:Superty,2017-01-13],[user:vmrajas,2017-01-13] ↵
↵
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**.↵
↵
We can also simplify the definition of $f_{r+1}$ as: ↵
$$f_{r+1}(n) = \sum_{d\|n} f_r(d)$$↵
↵
Since $f_0$ is a multiplicative function, $f_{r+1}$ is also a multiplicative function. (by property of multiplicative functions)↵
↵
For each query, factorize $n$.↵
↵
Now, since $f_r$ is a multiplicative function, if $n$ can be written as:↵
$$n=p_1^{e_1}p_2^{e_2}\ \cdots p_q^{e_q}$$↵
↵
Then $f_r(n)$ can be computed as:↵
$$f_r(n) = f_r(p_1^{e_1})*f_r(p_2^{e_2})* \cdots * f_r(p_q^{e_q})$$↵
↵
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:↵
↵
$$dp[r][x] = \sum_{i=0}^{x} dp[r-1][i]$$↵
↵
And now we can quickly compute $f_r(n)$ for each query as:↵
↵
$$f_r(n) = dp[r][e_1]*dp[r][e_2]* \cdots * dp[r][e_q]$$↵
↵
<spoiler summary="Author's code:">↵
~~~~~↵
↵
//Kyokai no Kanata //↵
//Written by Satyam Pandey//↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef pair<int,int> II;↵
typedef vector<II> VII;↵
typedef vector<int> VI;↵
typedef vector< VI > VVI;↵
typedef long long int LL;↵
↵
#define PB push_back↵
#define MP make_pair↵
#define F first↵
#define S second↵
#define SZ(a) (int)(a.size())↵
#define ALL(a) a.begin(),a.end()↵
#define SET(a,b) memset(a,b,sizeof(a))↵
↵
#define si(n) scanf("%d",&n)↵
#define dout(n) printf("%d\n",n)↵
#define sll(n) scanf("%lld",&n)↵
#define lldout(n) printf("%lld\n",n)↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
#define TRACE↵
↵
#ifdef TRACE↵
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)↵
template <typename Arg1>↵
void __f(const char* name, Arg1&& arg1){↵
cerr<<name<<" : "<<arg1<<endl;↵
}↵
template <typename Arg1, typename... Args>↵
void __f(const char* names,Arg1&& arg1,Args&&... args){↵
const char* comma=strchr(names+1,',');↵
cerr.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1,args...);↵
}↵
#else↵
#define trace(...)↵
#endif↵
float inf=std::numeric_limits<double>::infinity();↵
LL INF=std::numeric_limits<LL>::max();↵
//FILE *fin = freopen("in","r",stdin);↵
//FILE *fout = freopen("out","w",stdout);↵
const int R=int(1e6)+5,P=25,N=R,mod = int(1e9)+7;↵
int F[R][P],LP[N];↵
inline void seive(){↵
LP[1]=1;↵
for(int i=2;i<N;i++){↵
if(!LP[i])↵
for(int j=i;j<N;j+=i)↵
LP[j]=i; ↵
}↵
}↵
inline void precalc()↵
{↵
for(int i=0;i<R;i++) F[i][0] = 1; ↵
for(int i=1;i<P;i++) F[0][i] = 2;↵
for(int i=1;i<R;i++) ↵
for(int j=1;j<P;j++)↵
F[i][j] = (F[i][j-1] + F[i-1][j])%mod;↵
}↵
inline LL solve(int r,int n)↵
{↵
LL ans=1;↵
while(n!=1)↵
{↵
int cnt=0,p=LP[n];↵
while(n%p==0) n/=p,cnt++;↵
ans=(ans*F[r][cnt])%mod;↵
}↵
return ans;↵
}↵
int main()↵
{↵
seive();precalc();↵
int q;si(q);↵
int r,n;↵
while(q--)↵
{↵
si(r);si(n);↵
lldout(solve(r,n));↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
[757F — Team Rocket Rises Again ](http://www.codeforces.com/contest/757/problem/F)↵
------------------↵
**Author**: [user:tanujkhattar,2017-01-13] ↵
**Testers**: [user:shubhamvijay,2017-01-13], [user:tanmayc25,2017-01-13], [user:vmrajas,2017-01-13] ↵
↵
**Expected complexity**: $\mathcal{O}((N+M) \cdot logN)$ ↵
**Main idea**: Building Dominator tree on shortest path DAG. ↵
↵
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. ↵
↵
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$. ↵
↵
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. ↵
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$. ↵
You can read more about dominator tree [here](https://tanujkhattar.wordpress.com/2016/01/11/dominator-tree-of-a-directed-graph/). ↵
↵
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. ↵
↵
↵
↵
↵
<spoiler summary="Author's code:">↵
~~~~~↵
//Tanuj Khattar↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef pair<int,int> II;↵
typedef vector< II > VII;↵
typedef vector<int> VI;↵
typedef vector< VI > VVI;↵
typedef long long int LL;↵
↵
#define PB push_back↵
#define MP make_pair↵
#define F first↵
#define S second↵
#define SZ(a) (int)(a.size())↵
#define ALL(a) a.begin(),a.end()↵
#define SET(a,b) memset(a,b,sizeof(a))↵
↵
#define si(n) scanf("%d",&n)↵
#define dout(n) printf("%d\n",n)↵
#define sll(n) scanf("%lld",&n)↵
#define lldout(n) printf("%lld\n",n)↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
↵
#define TRACE↵
↵
#ifdef TRACE↵
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)↵
template <typename Arg1>↵
void __f(const char* name, Arg1&& arg1){↵
cerr << name << " : " << arg1 << std::endl;↵
}↵
template <typename Arg1, typename... Args>↵
void __f(const char* names, Arg1&& arg1, Args&&... args){↵
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);↵
}↵
#else↵
#define trace(...)↵
#endif↵
↵
//FILE *fin = freopen("in","r",stdin);↵
//FILE *fout = freopen("out","w",stdout);↵
const int N = int(1e5)+10;↵
const int M = int(2e5)+10;↵
const LL INF = LL(1e16);↵
namespace Dominator{↵
VI g[N],tree[N],rg[N],bucket[N];↵
int sdom[N],par[N],dom[N],dsu[N],label[N];↵
int arr[N],rev[N],T;//1-Based directed graph input↵
int Find(int u,int x=0){↵
if(u==dsu[u])return x?-1:u;↵
int v = Find(dsu[u],x+1);↵
if(v<0)return u;↵
if(sdom[label[dsu[u]]]<sdom[label[u]])↵
label[u] = label[dsu[u]];↵
dsu[u] = v;↵
return x?v:label[u];↵
}↵
void Union(int u,int v){ //Add an edge u-->v↵
dsu[v]=u; //yup,its correct :)↵
}↵
void dfs0(int u){↵
T++;arr[u]=T;rev[T]=u;↵
label[T]=T;sdom[T]=T;dsu[T]=T;↵
for(int i=0;i<SZ(g[u]);i++){↵
int w = g[u][i];↵
if(!arr[w])dfs0(w),par[arr[w]]=arr[u];↵
rg[arr[w]].PB(arr[u]);↵
}↵
}↵
void dfs1(int u,int p,int sub[]){↵
sub[u]=1;↵
for(auto w:tree[u])↵
if(w!=p)↵
dfs1(w,u,sub),sub[u]+=sub[w];↵
}↵
void reset(int n){↵
for(int i=1;i<=n;i++){↵
g[i].clear();rg[i].clear();tree[i].clear();arr[i]=0;↵
}↵
T=0;↵
}↵
void addEdge(int u,int v){↵
g[u].PB(v);↵
}↵
//Build Dominator tree(in main)↵
void get(int n,int root,int sub[]){↵
dfs0(root);n=T;↵
for(int i=n;i>=1;i--){↵
for(int j=0;j<SZ(rg[i]);j++)↵
sdom[i] = min(sdom[i],sdom[Find(rg[i][j])]);↵
if(i>1)bucket[sdom[i]].PB(i);↵
for(int j=0;j<SZ(bucket[i]);j++){↵
int w = bucket[i][j],v = Find(w);↵
if(sdom[v]==sdom[w])dom[w]=sdom[w];↵
else dom[w] = v;↵
}if(i>1)Union(par[i],i);↵
}↵
for(int i=2;i<=n;i++){↵
if(dom[i]!=sdom[i])dom[i]=dom[dom[i]];↵
tree[rev[i]].PB(rev[dom[i]]);↵
tree[rev[dom[i]]].PB(rev[i]);↵
}↵
dfs1(rev[1],rev[1],sub);↵
}//done :) ↵
}↵
int n,m,s,vis[N],sub[N];↵
VII g[N];VI P[N];↵
LL d[N];↵
int dijkstra(int root){↵
for(int i=1;i<=n;i++)d[i]=INF,P[i].clear();↵
Dominator::reset(n);d[root]=0;SET(vis,0);↵
set<pair<LL,int>> S;S.insert({d[root],root});↵
while(!S.empty()){↵
int u = S.begin()->S;↵
S.erase(S.begin());↵
if(vis[u])continue;↵
vis[u]=1;↵
for(auto w:g[u])↵
if(d[u] + w.S < d[w.F]){↵
d[w.F] = d[u] + w.S;↵
P[w.F].clear();P[w.F].PB(u);↵
S.insert({d[w.F],w.F});↵
}↵
else if(d[u]+w.S==d[w.F])↵
P[w.F].PB(u);↵
}↵
for(int i=1;i<=n;i++)↵
for(auto j : P[i])↵
Dominator::addEdge(j,i);↵
Dominator::get(n,root,sub);↵
int mx = 0;↵
for(int i=1;i<=n;i++)↵
if(i!=root)↵
mx = max(mx,sub[i]);↵
return mx;↵
}↵
int main()↵
{↵
si(n);si(m);si(s);↵
for(int i=1;i<=m;i++){↵
int u,v,w;↵
si(u);si(v);si(w);↵
g[u].PB({v,w});↵
g[v].PB({u,w});↵
}↵
dout(dijkstra(s));↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
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. ↵
For more details on this approach you can look at [user:moejy0viiiiiv,2017-01-13]'s solution [here](http://codeforces.net/contest/757/submission/23761400). ↵
↵
[757G — Can Bash Save the Day? ](http://www.codeforces.com/contest/757/problem/G)↵
------------------↵
**Author**: [user:tanujkhattar,2017-01-13] ↵
**Testers**: [user:Toshad,2017-01-13], [user:abhinavaggarwal,2017-01-13] ↵
↵
**Expected complexity**: $\mathcal{O}((N+Q) \cdot logN)$ ↵
**Main idea**: Making the Centroid Tree Persistent. ↵
↵
### Simpler Problem↵
↵
First let's try to solve a much simpler problem given as follows. ↵
↵
**Question:** Given a weighted tree, initially all the nodes of the given tree are inactive. We need to support the following operations fast : ↵
$Query \ v$ : Report the sum of distances of all active nodes from node $v$ in the given tree. ↵
$Activate \ v$ : Mark node $v$ to be an active node. ↵
↵
**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/) ↵
↵
### Solution Idea ↵
↵
- 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)$ ↵
- 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. ↵
- 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 $\mathcal{O}(logN)$ time by looking at it’s ancestors. ↵
- To store a copy of the centroid tree for each $i$, we need to make it persistent. ↵
↵
### Persistent Centroid Tree : Key Ideas↵
↵
- Important thing to note is that single update in the centroid tree affects only the ancestors of the node in the tree. ↵
- Since height of the centroid tree is $\mathcal{O}(logN)$, each update affects only $\mathcal{O}(logN)$ other nodes in the centroid tree. ↵
- 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 $\mathcal{O}(number \ of \ children)$ for each affected node and this number could be as large as $N$, hence it could take $\mathcal{O}(N)$ time in total ! ↵
↵
### Binarizing the Input Tree↵
↵
- 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 $\mathcal{O}(N)$. ↵
- The dummy nodes are added such that the structure of the tree is preserved and weights of the edges added are set to $0$. ↵
- 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 : ↵
- 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$.↵
- 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$. ↵
- 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 $\mathcal{O}(N)$ new nodes before degree of each node in the tree is $<=3$. ↵
↵
### Conclusion↵
↵
Hence we perform centroid decomposition of this transformed tree $T'$. The centroid tree formed would have the following properties.↵
↵
- The height of the centroid tree is $\mathcal{O}(logN)$ ↵
- Each node in the centroid tree has $\leq 3$ children.↵
↵
Now we can easily make this tree persistent by path-copying approach. ↵
To handle the updates,↵
↵
- **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 $\mathcal{O}(logN)$ new nodes. See author's code below for more details. ↵
- **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 $\mathcal{O}(logN)$ nodes for each update. See testers's code below for more details. ↵
↵
↵
<spoiler summary="Author's code:">↵
~~~~~↵
//Tanuj Khattar↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef pair<int,int> II;↵
typedef vector< II > VII;↵
typedef vector<int> VI;↵
typedef vector< VI > VVI;↵
typedef long long int LL;↵
↵
#define PB push_back↵
#define MP make_pair↵
#define F first↵
#define S second↵
#define SZ(a) (int)(a.size())↵
#define ALL(a) a.begin(),a.end()↵
#define SET(a,b) memset(a,b,sizeof(a))↵
↵
#define si(n) scanf("%d",&n)↵
#define dout(n) printf("%d\n",n)↵
#define sll(n) scanf("%lld",&n)↵
#define lldout(n) printf("%lld\n",n)↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
↵
#define TRACE↵
↵
#ifdef TRACE↵
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)↵
template <typename Arg1>↵
void __f(const char* name, Arg1&& arg1){↵
cerr << name << " : " << arg1 << std::endl;↵
}↵
template <typename Arg1, typename... Args>↵
void __f(const char* names, Arg1&& arg1, Args&&... args){↵
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);↵
}↵
#else↵
#define trace(...)↵
#endif↵
↵
//FILE *fin = freopen("in","r",stdin);↵
//FILE *fout = freopen("out","w",stdout);↵
const int MAXN = int(2e5)+10;↵
const int MAXQ = int(2e5)+10;↵
const int N = 2*MAXN;↵
const int M = 2*N;↵
int A[N]; //the permutation given↵
int last[N],prv[M],nxt[M],to[M],deg[N],W[M],root[N];↵
namespace tree{↵
int sz,edge,vis[N];↵
void addEdge(int u,int v,int w = 0){↵
prv[edge] = last[u];W[edge] = w;↵
if(last[u]!=-1)nxt[last[u]] = edge;↵
last[u] = edge;↵
to[edge] = v;↵
edge++;↵
}↵
void addEdge1(int u,int v,int e){↵
prv[e] = last[u];nxt[e] = -1;↵
if(last[u]!=-1)nxt[last[u]] = e;↵
last[u] = e;↵
to[e] = v;↵
}↵
void deleteEdge(int u,int e){↵
if(nxt[e]!=-1)prv[nxt[e]] = prv[e];↵
if(prv[e]!=-1)nxt[prv[e]] = nxt[e];↵
if(last[u] == e) last[u] = prv[e];↵
}↵
void changeEdge(int u,int v,vector<int> edges){↵
//assert(SZ(edges) == 3);assert(deg[u] > 3);↵
sort(ALL(edges));reverse(ALL(edges));↵
for(auto e : edges)↵
deleteEdge(u,e);↵
last[v] = last[u];↵
last[u] = -1;↵
for(auto e : edges)↵
addEdge1(u,to[e],e);↵
}↵
void pre(){↵
SET(last,-1);SET(nxt,-1);↵
SET(prv,-1);SET(to,-1);↵
}↵
//binarize the give tree.should be called from a leaf node.↵
void binarize(int u,int p,int edge){↵
vis[u]=1;↵
if(deg[u] > 3){↵
addEdge(u,++sz);↵
deg[sz] = deg[u] - 1;↵
set<int> temp;temp.insert(edge^1);↵
int e = last[u];↵
while(SZ(temp) < 3){↵
temp.insert(e);↵
e = prv[e];↵
}↵
changeEdge(u,sz,vector<int>(temp.begin(),temp.end()));↵
deg[u] = 3;↵
addEdge(sz,u);↵
}↵
for(int e = last[u];e >= 0; e = prv[e]){↵
if(!vis[to[e]])↵
binarize(to[e],u,e);↵
else to[e] = p;↵
}↵
}↵
}↵
namespace Centroid{↵
const int LOGN = 19;↵
const int MAXC = N + (MAXN + MAXQ)*LOGN;↵
int sub[N],nn,done[M],C[MAXC][3],L[N],R[N],idx[N],len[N],T,cnt[MAXC],lvl,IDX[MAXC];↵
LL sum[MAXC],cntbn[MAXC],dist[LOGN][N];↵
void dfs1(int u,int p){↵
sub[u]=1;nn++;↵
for(int e = last[u];e >= 0; e = prv[e]){↵
int w = to[e];↵
if(w!=p && !done[e])↵
dfs1(w,u),sub[u]+=sub[w];↵
}↵
}↵
int dfs2(int u,int p){↵
for(int e = last[u];e >= 0; e = prv[e]){↵
if(done[e])continue;int w = to[e];↵
if(w!=p && sub[w]>nn/2)↵
return dfs2(w,u);↵
}return u;↵
}↵
void dfs(int u,int p){↵
for(int e = last[u];e >= 0; e = prv[e]){↵
if(done[e] || to[e]==p)continue;↵
dist[lvl][to[e]] = dist[lvl][u] + W[e];↵
dfs(to[e],u);↵
}↵
}↵
int decompose(int root,int p,int l = 0){↵
nn=0;dfs1(root,root);↵
root=dfs2(root,root);↵
lvl = l;dfs(root,root);↵
idx[root] = ++T;↵
int id = idx[root];IDX[T] = T;↵
L[id] = T;↵
for(int e = last[root];e >= 0;e = prv[e]){↵
if(done[e])continue;↵
assert(!done[e^1]);↵
done[e]=done[e^1]=1;↵
int c = decompose(to[e],root,l+1);↵
assert(len[id] < 3);↵
C[id][len[id]++] = idx[c];↵
}↵
R[id] = T;↵
return root;↵
}↵
int update(int x,int id,int lvl=0){↵
int ID = ++T;↵
cnt[ID] = cnt[id] + 1;↵
sum[ID] = sum[id] + dist[lvl][x];↵
IDX[ID] = IDX[id];↵
for(int i=0;i<len[IDX[id]];i++)↵
if(L[IDX[C[id][i]]] <= idx[x] && idx[x] <= R[IDX[C[id][i]]]){↵
C[ID][i] = update(x,C[id][i],lvl+1);↵
cntbn[C[ID][i]] = cntbn[C[id][i]] + dist[lvl][x];↵
}↵
else C[ID][i] = C[id][i];↵
return ID;↵
}↵
LL query(int x,int id,int lvl=0){↵
LL ret = sum[id];↵
for(int i=0;i<len[IDX[id]];i++)↵
if(L[IDX[C[id][i]]] <= idx[x] && idx[x] <= R[IDX[C[id][i]]])↵
ret += query(x,C[id][i],lvl+1) - cntbn[C[id][i]] + (cnt[id] - cnt[C[id][i]])*dist[lvl][x];↵
return ret;↵
}↵
}↵
void binarize(int n){↵
int root = -1;↵
for(int i=1;i<=n;i++)↵
if(deg[i] == 1)↵
root = i;↵
tree::binarize(root,root,-1);↵
}↵
int main()↵
{↵
tree::pre();↵
int n,q;↵
si(n);si(q);↵
tree::sz = n;↵
for(int i=1;i<=n;i++)si(A[i]);↵
for(int i=1;i<n;i++){↵
int u,v,w;↵
si(u);si(v);si(w);↵
tree::addEdge(u,v,w);↵
tree::addEdge(v,u,w);↵
deg[u]++;deg[v]++;↵
}↵
//binarize the given tree↵
binarize(n);↵
//build the centroid tree.↵
Centroid::decompose(1,-1);↵
root[0] = 1;↵
//make it persistent and handle the queries.↵
for(int i=1;i<=n;i++)↵
root[i] = Centroid::update(A[i],root[i-1]);↵
const int MOD = (1 << 30);↵
LL ans = 0;↵
while(q--){↵
int t;si(t);↵
if(t==1){↵
int l,r,v;↵
si(l);si(r);si(v);↵
l = l ^ ans;↵
r = r ^ ans;↵
v = v ^ ans;↵
ans = Centroid::query(v,root[r])-Centroid::query(v,root[l-1]);↵
lldout(ans);↵
ans = ans % MOD;↵
}↵
else{↵
int x;si(x);x = x ^ ans;↵
root[x] = Centroid::update(A[x+1],root[x-1]);↵
swap(A[x],A[x+1]);↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Testers's code:">↵
~~~~~↵
//Toshad Salwekar↵
#include<bits/stdc++.h>↵
#define f(i,a,n) for(int i=a;i<n;i++)↵
#define S second↵
#define F first↵
#define Sc(n) scanf("%lld",&n)↵
#define scc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)↵
#define sp(a) scanf("%lld %lld",&a.first,&a.second)↵
#define pb push_back↵
#define mp make_pair↵
#define lb lower_bound↵
#define ub upper_bound↵
#define all(a) a.begin(),a.end()↵
#define sc(n) scanf("%d",&n)↵
#define It iterator↵
#define SET(a,b) memset(a,b,sizeof(a))↵
#define DRT() int t; cin>>t; while(t--)↵
// inbuilt functions↵
// __gcd, __builtin_ffs, (returns least significant 1-bit, __builtin_ffsll(1)=1)↵
// __builtin_clz, (returns number of leading zeroes in ↵
// __builtin_popcount,↵
using namespace std;↵
typedef long long LL;↵
typedef pair<int,LL> PII;↵
typedef vector<int> vi;↵
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)↵
#define trv(s,it) for(auto it:s)↵
#define TRACE↵
↵
#ifdef TRACE↵
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)↵
template <typename Arg1>↵
void __f(const char* name, Arg1&& arg1){↵
cerr << name << " : " << arg1 << std::endl;↵
}↵
template <typename Arg1, typename... Args>↵
void __f(const char* names, Arg1&& arg1, Args&&... args){↵
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);↵
}↵
#else↵
#define trace(...)↵
#endif↵
#define N 400005↵
#define LOGN 20↵
const int MAX = N*LOGN;↵
const int MOD = (1<<30);↵
int cn[N],nn,par[N],arr[N],centroid,C,tot,anc[N];↵
LL dis[LOGN][N];↵
vector<PII> tree[N];↵
bool mark[N]; stack<int> st;↵
struct node↵
{ int id,cn,len; LL sum,psum;↵
node* child[4];↵
}*pers[N];↵
node BUFF[MAX];↵
int buf_len;↵
int dfs1(int i,int p)↵
{ int r=1,mx=0,t;↵
for(auto it:tree[i])↵
if(it.F!=p && !mark[it.F])↵
r+=dfs1(it.F,i);↵
cn[i]=r;↵
return r;↵
}↵
int dfs2(int i,int p,int num)↵
{ for(auto it:tree[i])↵
if(cn[it.F]>num/2 && !mark[it.F] && it.F!=p)↵
return dfs2(it.F,i,num);↵
return i;↵
}↵
void dfs(int i,int p,LL d)↵
{ for(auto it:tree[i])↵
if(it.F!=p && !mark[it.F])↵
dfs(it.F,i,d+it.S);↵
dis[C][i]=d;↵
}↵
void dec(int root, node* p,int c)↵
{ dfs1(root,root);↵
int cen=dfs2(root,root,cn[root]); //cen is centroid of current subtree↵
C=c;↵
dfs(cen,cen,0LL);↵
mark[cen]=1;↵
node* tmp= BUFF + buf_len++;↵
tmp->id=cen;↵
tmp->cn=0; tmp->len=0;↵
tmp->sum=0; ↵
if(p!=NULL)↵
{ p->child[p->len++]=tmp;↵
par[cen]=p->id;↵
}↵
else↵
{ pers[0]=tmp; //This means cen is the centroid↵
centroid=cen;↵
}↵
for(auto it:tree[cen])↵
if(!mark[it.F])↵
dec(it.F,tmp,c+1);↵
}↵
node* persist(node* root, int i,int l)↵
{ ↵
node* tmp= BUFF + buf_len++;↵
tmp->id=root->id;↵
tmp->sum=root->sum + dis[l][i];↵
if(l)↵
tmp->psum=root->psum + dis[l-1][i];↵
tmp->cn=root->cn + 1;↵
tmp->len=0;↵
f(j,0,root->len)↵
if(!st.empty() && (root->child[j])->id==st.top())↵
{ st.pop();↵
tmp->child[tmp->len++]=persist(root->child[j],i,l+1);↵
}↵
else↵
tmp->child[tmp->len++]=root->child[j];↵
return tmp;↵
}↵
LL query(node* root, int i,int l)↵
{ LL ans=0;↵
ans+=(root->cn)*dis[l][i]+root->sum; // Add all nodes in range which are in subtree(in centroid tree) of current node↵
f(j,0,root->len)↵
if(!st.empty() && root->child[j]->id==st.top())↵
{ st.pop();↵
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↵
ans+=query(root->child[j],i,l+1); // in same subtree as the query node).↵
}↵
return ans;↵
}↵
void binarise(unordered_map<int,LL> &add,int i,PII p,bool fl)↵
{ unordered_map<int,LL> tmp;↵
mark[i]=1;↵
if(fl) // fl=1 for those nodes which were not in original tree↵
{ add.erase(p.F);↵
tree[i].pb(p);↵
tree[i].pb(*(add.begin()));↵
add.erase(add.begin());↵
if(add.size()>1) // Need to create more nodes↵
{ tree[i].pb(mp(tot++,0LL));↵
binarise(add,tot-1,mp(i,0LL),1);↵
}↵
else ↵
{ tree[i].pb(*(add.begin()));↵
binarise(tmp,tree[i][2].F,mp(i,tree[i][2].S),0);↵
}↵
binarise(tmp,tree[i][1].F,mp(i,tree[i][1].S),0);↵
}↵
else if(tree[i].size()>3)↵
{ int t=0;bool fl=0;↵
if(tree[i][t].F==p.F)↵
t++;↵
f(j,t,tree[i].size())↵
if(mark[tree[i][j].F] && tree[i].size()==4) // This means that tree[i][j].F is the parent in original tree↵
fl=1;↵
if(fl) // Only has ↵
{ f(j,0,tree[i].size())↵
if(tree[i][j]!=p && !mark[tree[i][j].F])↵
binarise(tmp,tree[i][j].F,mp(i,tree[i][j].S),0);↵
else if(mark[tree[i][j].F])↵
tree[i][j]=p;↵
return;↵
}↵
if(mark[tree[i][t].F])↵
t++;↵
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.↵
f(j,0,tree[i].size())↵
if(j==t);↵
else if(!mark[tree[i][j].F] && tree[i][j].F!=p.F)↵
tmp.insert(tree[i][j]);↵
else if(mark[tree[i][j].F]) //Replace original parent with new parent↵
tree[i][j]=p;↵
PII tm=tree[i][t];↵
tree[i].clear();↵
if(i!=1) // 1 is root. For all others, add parent.↵
tree[i].pb(p); ↵
tree[i].pb(tm); ↵
tree[i].pb(mp(tot++,0LL)); // Add new extra node↵
binarise(tmp,tot-1,mp(i,0LL),1);↵
}↵
else↵
f(j,0,tree[i].size())↵
if(tree[i][j]!=p && !mark[tree[i][j].F])↵
binarise(tmp,tree[i][j].F,mp(i,tree[i][j].S),0);↵
else if(mark[tree[i][j].F]) //Replace original with new parent↵
tree[i][j]=p;↵
}↵
↵
int main()↵
{↵
int n,q; LL a,b,c;↵
cin>>n>>q;↵
tot=n+1;↵
f(i,1,n+1)↵
sc(arr[i]);↵
f(i,1,n)↵
{ scc(a,b,c);↵
tree[a].pb(mp(b,c));↵
tree[b].pb(mp(a,c));↵
}↵
unordered_map<int,LL> stmp;↵
binarise(stmp,1,mp(0,0LL),0);↵
SET(mark,0);↵
dec(1,NULL,0);↵
f(i,1,n+1)↵
{↵
int p=arr[i];↵
while(p!=centroid) //push all nodes to be added in a stack↵
{ st.push(p); ↵
p=par[p];↵
}↵
pers[i]=persist(pers[i-1],arr[i],0);↵
}↵
LL an = 0;↵
f(i,1,q+1)↵
{ Sc(a);↵
Sc(b);↵
if(a==1)↵
{ Sc(c); Sc(a);↵
b = b ^ an; c = c ^ an; a = a ^ an;↵
int p=a;↵
an=0;↵
while(p!=centroid) //push all nodes to be queried in a stack↵
{ st.push(p);↵
p=par[p];↵
}↵
an-=query(pers[b-1],a,0);↵
p=a;↵
while(p!=centroid) //push all nodes to be queried in a stack↵
{ st.push(p);↵
p=par[p];↵
}↵
an+=query(pers[c],a,0);↵
printf("%lld\n",an);↵
an %= MOD;↵
}↵
else ↵
{ b = b ^ an;↵
int p=arr[b],lca=centroid,h=centroid;↵
while(p!=centroid)↵
{ anc[p]=i; //mark all ancestors of arr[b]↵
p=par[p];↵
}↵
p=arr[b+1];↵
while(p!=centroid)↵
{ if(anc[p]==i)↵
{ lca=p; break; }↵
h=p; // h is the highest ancestor of arr[b+1] which is not an ancestor of arr[b]↵
p=par[p];↵
}↵
node *rt1=pers[b], *rt2=pers[b+1], *rt=pers[b-1];↵
int l=0,k=-1;↵
while(rt->id!=lca) //traverse down to lca in all 3 centroid trees.↵
{ rt1->sum -= dis[l][arr[b]] - dis[l][arr[b+1]];↵
if(l) ↵
rt1->psum -= dis[l-1][arr[b]] - dis[l-1][arr[b+1]]; ↵
l++;↵
f(j,0,rt1->len)↵
if(anc[rt1->child[j]->id]==i)↵
{ rt1=rt1->child[j];↵
break;↵
}↵
f(j,0,rt2->len)↵
if(anc[rt2->child[j]->id]==i)↵
{ rt2=rt2->child[j];↵
break;↵
}↵
f(j,0,rt->len)↵
if(anc[rt->child[j]->id]==i)↵
{ rt=rt->child[j];↵
break;↵
}↵
}↵
rt1->sum-=dis[l][arr[b]]-dis[l][arr[b+1]]; //update lca too↵
if(l) ↵
rt1->psum-=dis[l-1][arr[b]]-dis[l-1][arr[b+1]];↵
↵
/* This is the swapping part. ↵
* b1child represents the child containing arr[b], ↵
* b2child represents the child containing arr[b+1] and ↵
* bchild represents the child containing arr[b] in persistent centroid tree of first b-1 elements↵
* 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. ↵
* 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].↵
* */↵
node *b1child=NULL,*b2child=NULL,*bchild=NULL;↵
f(j,0,rt->len) //find bchild It may not exist if arr[b] = lca↵
if(anc[rt->child[j]->id]==i)↵
bchild=rt->child[j];↵
f(j,0,rt1->len)↵
if(anc[rt1->child[j]->id]==i) //find b1child. It may not exist if arr[b] = lca↵
{ b1child=rt1->child[j]; k=j; }↵
int vv=0;↵
if(b1child!=NULL) // vv is used to handle the case where b1child = NULL↵
vv=b1child->id;↵
f(j,0,rt2->len)↵
if(rt2->child[j]->id==h) //find b2child. It may not exist if arr[b+1] = lca↵
b2child=rt2->child[j];↵
else if(rt2->child[j]->id==vv) ↵
rt2->child[j]=b1child;↵
if(k>=0) //Again, check if b1child exists.↵
rt1->child[k]=bchild;↵
f(j,0,rt1->len)↵
if(rt1->child[j]->id==h)↵
rt1->child[j]=b2child;↵
swap(arr[b],arr[b+1]);↵
}↵
↵
}↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Hope you enjoyed the problemset! Any feedback is appreciatd! :) ↵
