codeforces-scrape

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

960.md (16354B)


      1 Source: https://codeforces.com/blog/entry/58802
      2 
      3 Tutorial is loading...
      4 
      5 Set by : [vntshh](/profile/vntshh "Candidate Master vntshh")
      6 
      7 **Setter's solution**
      8 
      9 ```
     10 #include<bits/stdc++.h>
     11 #define rep(i,start,lim) for(lld i=start;i<lim;i++)
     12 #define repd(i,start,lim) for(lld i=start;i>=lim;i--)
     13 #define scan(x) scanf("%lld",&x)
     14 #define print(x) printf("%lld ",x)
     15 #define f first
     16 #define s second
     17 #define pb push_back
     18 #define mp make_pair
     19 #define br printf("\n")
     20 #define sz(a) lld((a).size())
     21 #define YES printf("YES\n")
     22 #define NO printf("NO\n")
     23 #define all(c) (c).begin(),(c).end()
     24 #define INF         1011111111
     25 #define LLINF       1000111000111000111LL
     26 #define EPS         (double)1e-10
     27 #define MOD         1000000007
     28 #define PI          3.14159265358979323
     29 using namespace std;
     30 typedef long double ldb;
     31 typedef long long lld;
     32 lld powm(lld base,lld exp,lld mod=MOD) {lld ans=1;while(exp){if(exp&1) ans=(ans*base)%mod;exp>>=1,base=(base*base)%mod;}return ans;}
     33 lld ctl(char x,char an='a') {return (lld)(x-an);}
     34 char ltc(lld x,char an='a') {return (char)(x+an);}
     35 #define bit(x,j) ((x>>j)&1)
     36 typedef vector<lld> vlld;
     37 typedef pair<lld,lld> plld;
     38 typedef map<lld,lld> mlld;
     39 typedef set<lld> slld;
     40 #define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
     41 #define mxm(a,b) a = max(a,b)
     42 #define mnm(a,b) a = min(a,b)
     43 #define endl '\n'
     44 #define fre freopen("1.in","r",stdin); freopen("1.out","w",stdout);
     45 #define N 1000005
     46 int main()
     47 {
     48     //sync;
     49     string s;
     50     map<char,lld> m;
     51     cin>>s;
     52     lld k = sz(s);
     53     string tmp = "";
     54     tmp += s[0];
     55     rep(i,1,k) if(s[i]!=s[i-1]) tmp+=s[i];
     56     rep(i,0,k) m[s[i]]++;
     57     if(tmp != "abc") return 0*NO;
     58     if(m['c']!=m['a'] and m['c']!=m['b']) return 0*NO;
     59     if(m['a']>=1 and m['b']>=1) return 0*YES;
     60     else return 0*NO;
     61     return 0;
     62 }
     63 ```
     64 
     65 Tutorial is loading...
     66 
     67 Set by : [AakashHanda](/profile/AakashHanda "Candidate Master AakashHanda")
     68 
     69 **Setter's solution**
     70 
     71 ```
     72 #include<bits/stdc++.h>
     73 using namespace std;
     74 
     75 typedef long long ll;
     76 
     77 priority_queue<ll> pq;
     78 
     79 int main(){
     80     int n, k1, k2, k;
     81     cin>>n>>k1>>k2;
     82     k = k1+k2;
     83     vector<ll> a(n), b(n), arr(n);
     84     for(int i=0 ; i<n ; ++i)
     85         cin>>a[i];
     86     for(int i=0 ; i<n ; ++i){
     87         cin>>b[i];
     88         arr[i] = abs(a[i]-b[i]);
     89         pq.push(arr[i]);
     90     }
     91     while(k>0){
     92         ll curr = pq.top();
     93         pq.pop();
     94         pq.push(abs(curr-1));
     95         k--;
     96     }
     97     ll ans = 0;
     98     while(!pq.empty()){
     99         ll curr = pq.top();
    100         ans += (curr*curr);
    101         pq.pop();
    102     }
    103     cout<<ans;
    104 }
    105 ```
    106 
    107 Tutorial is loading...
    108 
    109 Set by : [7dan](/profile/7dan "Expert 7dan")
    110 
    111 **Setter's solution**
    112 
    113 ```
    114 #include<bits/stdc++.h>
    115 #define rep(i,start,lim) for(lld i=start;i<lim;i++)
    116 #define repd(i,start,lim) for(lld i=start;i>=lim;i--)
    117 #define scan(x) scanf("%lld",&x)
    118 #define print(x) printf("%lld ",x)
    119 #define f first
    120 #define s second
    121 #define pb push_back
    122 #define mp make_pair
    123 #define br printf("\n")
    124 #define sz(a) lld((a).size())
    125 #define YES printf("YES\n")
    126 #define NO printf("NO\n")
    127 #define all(c) (c).begin(),(c).end()
    128 #define INF         1011111111
    129 #define LLINF       1000111000111000111LL
    130 #define EPS         (double)1e-10
    131 #define MOD         1000000007
    132 #define PI          3.14159265358979323
    133 using namespace std;
    134 typedef long double ldb;
    135 typedef long long lld;
    136 lld powm(lld base,lld exp,lld mod=MOD) {lld ans=1;while(exp){if(exp&1) ans=(ans*base)%mod;exp>>=1,base=(base*base)%mod;}return ans;}
    137 lld ctl(char x,char an='a') {return (lld)(x-an);}
    138 char ltc(lld x,char an='a') {return (char)(x+an);}
    139 #define bit(x,j) ((x>>j)&1)
    140 typedef vector<lld> vlld;
    141 typedef pair<lld,lld> plld;
    142 typedef map<lld,lld> mlld;
    143 typedef set<lld> slld;
    144 #define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
    145 #define mxm(a,b) a = max(a,b)
    146 #define mnm(a,b) a = min(a,b)
    147 #define endl '\n'
    148 #define fre freopen("1.in","r",stdin); freopen("1.out","w",stdout);
    149 #define N 1000005
    150 int main()
    151 {
    152     //sync;
    153     lld x,d;
    154     vector<lld> ans;
    155     cin>>x>>d;
    156     lld num = 1, cnt = 0;
    157     repd(i,60,1) if(bit(x,i)) {
    158         rep(j,0,i) ans.pb(num);
    159         cnt++;
    160         num+=(d+1);
    161     }
    162     while(cnt--) ans.pb(num),num+=(d+1);
    163     if(x%2) ans.pb(num);
    164     cout<<sz(ans)<<endl;
    165     for(auto i:ans) cout<<i<<" ";
    166     return 0;
    167 }
    168 ```
    169 
    170 Tutorial is loading...
    171 
    172 Set by : [Vicennial](/profile/Vicennial "Candidate Master Vicennial")
    173 
    174 **Setter's solution**
    175 
    176 ```
    177 //Gvs Akhil (Vicennial)
    178 #include<bits/stdc++.h>
    179 #define int long long
    180 #define pb push_back
    181 #define eb emplace_back
    182 #define mp make_pair
    183 #define mt make_tuple
    184 #define ld(a) while(a--)
    185 #define tci(v,i) for(auto i=v.begin();i!=v.end();i++)
    186 #define tcf(v,i) for(auto i : v)
    187 #define all(v) v.begin(),v.end()
    188 #define rep(i,start,lim) for(long long (i)=(start);i<(lim);i++)
    189 #define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
    190 #define osit ostream_iterator
    191 #define INF 		0x3f3f3f3f
    192 #define LLINF       1000111000111000111LL
    193 #define PI 			3.14159265358979323
    194 #define endl '\n'
    195 #define trace1(x)                cerr<<#x<<": "<<x<<endl
    196 #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
    197 #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
    198 #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
    199 #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
    200 #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
    201 const int N=1000006;
    202 using namespace std;
    203 typedef vector<int> vi;
    204 typedef vector<vi> vvi;
    205 typedef long long ll;
    206 typedef vector<long long> vll;
    207 typedef vector<vll> vvll;
    208 typedef long double ld;
    209 typedef pair<int,int> ii;
    210 typedef vector<ii> vii;
    211 typedef vector<vii> vvii;
    212 typedef tuple<int,int,int> iii;
    213 typedef set<int> si;
    214 typedef complex<double> pnt;
    215 typedef vector<pnt> vpnt;
    216 typedef priority_queue<ii,vii,greater<ii> > spq;
    217 const ll MOD=1000000007LL;
    218 template<typename T> T gcd(T a,T b){if(a==0) return b; return gcd(b%a,a);}
    219 template<typename T> T power(T x,T y,ll m=MOD){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}
    220 int shift[66];
    221 inline int getlev(int x){
    222 	int z=__builtin_clzll(x);
    223 	return 64-z;
    224 }
    225 inline int getmod(int x){
    226 	return (1LL<<(x-1));
    227 }
    228 void addshift(int x,int k){
    229 	int m=getmod(x);
    230 	if(k>=m) k%=m;
    231 	shift[x]+=k;
    232 	if(shift[x]>=m) shift[x]-=m;
    233 	if(shift[x]<0) shift[x]+=m;	
    234 }
    235 int getorig(int V,int l){
    236 	int fval=(1LL<<(l-1)); // 2^(L-1)
    237 	int mod=getmod(l);
    238 	int P= V-fval; 
    239 	int Z= fval+((P-shift[l])%mod + mod)%mod;
    240 	return Z;
    241 }
    242 int32_t main(){
    243 	sync;
    244 	int q; cin>>q;
    245 	while(q--){
    246 		int t,x,k;
    247 		cin>>t>>x;
    248 		int l=getlev(x);
    249 		if(t==1){ 
    250 			cin>>k; k%=getmod(l);
    251 			addshift(l,k);
    252 		}
    253 		else if(t==2){// propogating
    254 			cin>>k; 
    255 			k%=getmod(l);
    256 			if(k<0) k+=getmod(l);
    257 			 int curr=1;
    258 			for(int i=l;i<=60;i++){
    259 				addshift(i,k*curr);
    260 				curr<<=1;
    261 			}
    262 		}
    263 		else{ // printing
    264 			int P= x - (1LL<<(l-1)); // Finding index in array
    265 			int V= (1LL<<(l-1)) + ((P+shift[l])%(1LL<<(l-1)) + (1LL<<(l-1)) )%(1ll<<(l-1)); //Finding original value at the new index of X after performing the shift.
    266 			for(int i=l;i>=1;i--){
    267 				int Z = getorig(V,i); // Finding the current value
    268 				cout<<Z<<" "; // printing the current value
    269 				V>>=1; // dividing the original value by 2 to get its parent value
    270 			}
    271 			cout<<endl;
    272 		}
    273 	}
    274 }
    275 ```
    276 
    277 Tutorial is loading...
    278 
    279 Set by : [rohitranjan017](/profile/rohitranjan017 "Expert rohitranjan017")
    280 
    281 **Setter's solution**
    282 
    283 ```
    284 #include<bits/stdc++.h>
    285 using namespace std;
    286 typedef long long ll;
    287 const int M=1000005,mod=1e9+7;
    288 vector<int> adj[M];
    289 int par[M],lev[M];
    290 ll v[M];
    291 ll e[M],o[M];
    292 ll ans,res,n;
    293 ll powmod(ll base, ll exponent)
    294 { 
    295 	//cout<<base<<" "<<exponent<<endl;
    296 
    297 	ll ans=1;
    298 	
    299 		while(exponent)
    300 		{ 
    301 			while(exponent%2==0)
    302 			{
    303 				base=(base*base)%mod;
    304 				exponent/=2;
    305 			}
    306 			
    307 			exponent--;
    308 			ans=(ans*base)%mod;
    309 		}
    310 		
    311 	return ans;
    312 }
    313 void dfs(int x,int depth)
    314 {
    315 	//o[x]++;
    316 
    317 	lev[x]=depth;
    318 	
    319 	int cno=0;
    320 
    321 	for(int i=0;i<adj[x].size();i++)
    322 	{
    323 		int c=adj[x][i];
    324 	
    325 		if(c!=par[x])
    326 		{
    327 			par[c]=x;
    328 	
    329 			dfs(c,depth+1);
    330 		
    331 			if(cno>0)
    332 			{
    333 				ans=( (ans+ 2*( o[x]*e[c]%mod - e[x]*o[c]%mod + mod)%mod*v[x]%mod)+mod )%mod;
    334 			}
    335 			
    336 			cno++;
    337 		
    338 			o[x]+=e[c];
    339 			e[x]+=o[c];
    340 		
    341 		}
    342 	
    343 	}
    344 	
    345 	o[x]++;
    346 
    347 	
    348 }
    349 int main()
    350 {
    351 	//freopen("o.out","r",stdin);
    352 
    353 	cin>>n;
    354 	
    355 	for(int i=1;i<=n;i++)
    356 	{
    357 		cin>>v[i];
    358 	}
    359 	
    360 	for(int i=1;i<n;i++)
    361 	{
    362 		int u,v;
    363 		
    364 		cin>>u>>v;
    365 		
    366 		adj[u].push_back(v);
    367 		adj[v].push_back(u);
    368 	}
    369 	
    370 	dfs(1,0); 
    371 	
    372 	//cout<<ans<<endl;
    373 	
    374 	for(int i=1;i<=n;i++)
    375 	{	
    376 		//cout<<"###"<<i<<endl;
    377 		if(lev[i]%2)
    378 		{
    379 			ans=((ans+2*(o[i]*(e[1]-o[i]+1)%mod - e[i]*(o[1]-e[i])%mod +mod)%mod*v[i]%mod)%mod+mod )%mod;
    380 		}
    381 		else
    382 		{
    383 			ans=((ans+2*(o[i]*(o[1]-o[i]+1)%mod - e[i]*(e[1]-e[i])%mod +mod)%mod*v[i]%mod)%mod+mod )%mod;
    384 		}
    385 		
    386 		//cout<<ans<<endl;
    387 		
    388 		ans=((ans-v[i])%mod+mod)%mod;
    389 		
    390 //		cout<<i<<" "<<ans<<endl;
    391 		//cout<<ans<<endl;
    392 	}
    393 	
    394 	cout<<ans<<endl;
    395 
    396 }
    397 ```
    398 
    399 Tutorial is loading...
    400 
    401 Set by : [kr_abhinav](/profile/kr_abhinav "Candidate Master kr_abhinav")
    402 
    403 **Setter's solution**
    404 
    405 ```
    406 #include <bits/stdc++.h>
    407 using namespace std;
    408 vector<map<int,int> > s;
    409 int getedgelen(int a, int w)
    410 {
    411     auto it = s[a].lower_bound(w);
    412     if(it == s[a].begin()) return 1;
    413     it--;
    414     return (it->second)+1;
    415 }
    416 int32_t main() {
    417     ios::sync_with_stdio(false);cin.tie(0);
    418     int n,m,a,b,w;
    419     cin>>n>>m;
    420     s.resize(n+1);
    421     int ans = 0;
    422     while(m--)
    423     {
    424         cin>>a>>b>>w;
    425         int val = getedgelen(a,w);
    426         if(getedgelen(b,w+1) > val)
    427             continue;
    428         s[b][w] = max(s[b][w],val);
    429         auto it = s[b].upper_bound(w);
    430         while(!(it==s[b].end() || it->second > val))
    431         {
    432             it = s[b].erase(it);
    433         }
    434         ans = max(ans,val);
    435     }
    436     cout<<ans;
    437     return 0;
    438 }
    439 ```
    440 
    441 Tutorial is loading...
    442 
    443 Set by : [apoorv_kulsh](/profile/apoorv_kulsh "Candidate Master apoorv_kulsh")
    444 
    445 **Setter's solution**
    446 
    447 ```
    448 #include <bits/stdc++.h>
    449 using namespace std;
    450 typedef long long ll;
    451 #define pb push_back
    452 const int mod = 998244353;
    453 const int root = 15311432;
    454 const int root_1 = 469870224;
    455 const int root_pw = 1 << 23;
    456 const int N = 400004;
    457 
    458 vector<int> v[N];
    459 
    460 ll modInv(ll a, ll mod = mod){
    461 	ll x0 = 0, x1 = 1, r0 = mod, r1 = a;
    462 	while(r1){
    463 		ll q = r0 / r1;
    464 		x0 -= q * x1; swap(x0, x1);
    465 		r0 -= q * r1; swap(r0, r1);
    466 	}
    467 	return x0 < 0 ? x0 + mod : x0;
    468 }
    469 
    470 void fft (vector<int> &a, bool inv) {
    471 	int n = (int) a.size();
    472 
    473 	for (int i=1, j=0; i<n; ++i) {
    474 		int bit = n >> 1;
    475 		for (; j>=bit; bit>>=1)
    476 			j -= bit;
    477 		j += bit;
    478 		if (i < j)
    479 			swap (a[i], a[j]);
    480 	}
    481 
    482 	for (int len=2; len<=n; len<<=1) {
    483 		int wlen = inv ? root_1 : root;
    484 		for (int i=len; i<root_pw; i<<=1)
    485 			wlen = int (wlen * 1ll * wlen % mod);
    486 		for (int i=0; i<n; i+=len) {
    487 			int w = 1;
    488 			for (int j=0; j<len/2; ++j) {
    489 				int u = a[i+j],  v = int (a[i+j+len/2] * 1ll * w % mod);
    490 				a[i+j] = u+v < mod ? u+v : u+v-mod;
    491 				a[i+j+len/2] = u-v >= 0 ? u-v : u-v+mod;
    492 				w = int (w * 1ll * wlen % mod);
    493 			}
    494 		}
    495 	}
    496 
    497 	if(inv) {
    498 		int nrev = modInv(n, mod);
    499 		for (int i=0; i<n; ++i)
    500 			a[i] = int (a[i] * 1ll * nrev % mod);
    501 	}
    502 }
    503 
    504 void pro(const vector<int> &a, const vector<int> &b, vector<int> &res) {
    505 	vector<int> fa(a.begin(), a.end()),  fb(b.begin(), b.end());
    506 	int n = 1;
    507 	while (n < (int) max(a.size(), b.size()))  n <<= 1;
    508 	n <<= 1;
    509 	fa.resize (n),  fb.resize (n);
    510 
    511 	fft(fa, false), fft (fb, false);
    512 	for (int i = 0; i < n; ++i)
    513 		fa[i] = 1LL * fa[i] * fb[i] % mod;
    514 	fft (fa, true);
    515 	res = fa;
    516 }
    517 
    518 int S(int n, int r) {
    519 
    520 	int nn = 1;
    521 	while(nn < n) nn <<= 1;
    522 
    523 	for(int i = 0; i < n; ++i) {
    524 		v[i].push_back(i);
    525 		v[i].push_back(1);
    526 	}
    527 	for(int i = n; i < nn; ++i) {
    528 		v[i].push_back(1);
    529 	}
    530 
    531 	for(int j = nn; j > 1; j >>= 1){
    532 		int hn = j >> 1;
    533 		for(int i = 0; i < hn; ++i){
    534 			pro(v[i], v[i + hn], v[i]);
    535 		}
    536 	}
    537 
    538 	return v[0][r];
    539 }
    540 
    541 int fac[N], ifac[N], inv[N];
    542 
    543 void prencr(){
    544 	fac[0] = ifac[0] = inv[1] = 1;
    545     for(int i = 2; i < N; ++i)
    546     	inv[i] = mod - 1LL * (mod / i) * inv[mod % i] % mod;
    547     for(int i = 1; i < N; ++i){
    548     	fac[i] = 1LL * i * fac[i - 1] % mod;
    549     	ifac[i] = 1LL * inv[i] * ifac[i - 1] % mod;
    550     }
    551 }
    552 
    553 int C(int n, int r){
    554 	return (r >= 0 && n >= r) ? (1LL * fac[n] * ifac[n - r] % mod * ifac[r] % mod) : 0;
    555 }
    556 
    557 int main(){
    558 	prencr();
    559 	int n, p, q;
    560 	cin >> n >> p >> q;
    561 	ll ans = C(p + q - 2, p - 1);
    562 	ans *= S(n - 1, p + q - 2);
    563 	ans %= mod;
    564 	cout << ans;
    565 }
    566 ```
    567 
    568 Tutorial is loading...
    569 
    570 Set by : [arnabsamanta](/profile/arnabsamanta "Expert arnabsamanta")
    571 
    572 **Setter's solution**
    573 
    574 ```
    575 #include <bits/stdc++.h>
    576 using namespace std;
    577 typedef long long ll;
    578 #define pb push_back
    579 const int N = 400004;
    580 
    581 int n;
    582 vector<int> e[N];
    583 int sz[N], par[N], sp[30][N];
    584 int V[N], L[N], CS[N];
    585 bool mark[N];
    586 
    587 struct tri {
    588 	long long A, B;
    589 	int C;
    590 };
    591 
    592 map<int, tri> nmp[N];
    593 
    594 long long D[N]; // Sum of Distances
    595 long long S[N]; // Sum of Depth
    596 int T[N]; // Count
    597 
    598 //======================================PRE-PROCESS=========================================
    599 
    600 void getLevel(int u, int p = -1){
    601 	sp[0][u] = p;
    602 	for(auto x : e[u]) if(x != p) {
    603 		L[x] = 1 + L[u];
    604 		getLevel(x, u);
    605 	}
    606 }
    607 
    608 void prepAncestor(){
    609 	for(int i = 1; (1 << i) <= n; ++i) {
    610 		for(int j = 1; j <= n; ++j) {
    611 			sp[i][j] = sp[i - 1][sp[i - 1][j]];
    612 		}
    613 	}
    614 }
    615 
    616 int dist(int u, int v){
    617 	if(L[u] < L[v]) swap(u, v);
    618 	int lgn = 0;
    619 	while((1 << lgn) < n) lgn++;
    620 	int ans = 0;
    621 	for(int i = lgn; i >= 0; --i){
    622 		if(L[u] - (1 << i) >= L[v]){
    623 			u = sp[i][u];
    624 			ans += (1 << i);
    625 		}
    626 	}
    627 	if(u == v) return ans;
    628 	for(int i = lgn; i >= 0; --i){
    629 		if(sp[i][u] != sp[i][v]){
    630 			ans += 1 << (i + 1);
    631 			u = sp[i][u];
    632 			v = sp[i][v];
    633 		}
    634 	}
    635 	return ans + 2;
    636 }
    637 
    638 //=================================CENTROID DECOMPOSITION===================================
    639 
    640 void getSize(int u, int p = -1) {
    641       sz[u] = 1;
    642       for(auto v : e[u]) if(v != p && !mark[v]) {
    643             getSize(v, u);
    644             sz[u] += sz[v];
    645       }
    646 }
    647  
    648 int getCentroid(int u, int p, int lim) {
    649       for(auto v : e[u]) if(v != p && !mark[v] && sz[v] > lim) {
    650             return getCentroid(v, u, lim);
    651       }
    652       return u;
    653 }
    654 
    655 void decompose(int u, int p = -1) {
    656       getSize(u);
    657       int cen = getCentroid(u, -1, sz[u] / 2);
    658       par[cen] = p == -1 ? cen : p;
    659       mark[cen] = true;
    660        
    661       for(auto v : e[cen]) if(v != p && !mark[v]) {
    662             decompose(v, cen);
    663       }
    664 }
    665 
    666 //==========================================QUERY-HANDLER===============================================
    667 
    668 void updAns(int u, int add) {
    669 
    670 	int Z = V[u];
    671 	
    672 	tri tY = nmp[u][Z];
    673 	ll ret = tY.A;
    674 	int y = u, x = par[u];
    675 	while(y != x) {
    676 		tri tX = nmp[x][Z];
    677 		ret += 1LL * (tX.C - tY.C) * dist(x, u) + (tX.A - tY.B);
    678 		y = x;
    679 		tY = tX;
    680 		x = par[x];
    681 	}
    682 	ret <<= 1;
    683 
    684 	int mul = add ? 1 : -1;
    685 	D[Z] += mul * ret;
    686 	S[Z] += mul * L[u];
    687 	T[Z] += mul;
    688 }
    689 
    690 void updTree(int u, bool add) {
    691 	int Z = V[u];
    692 	int mul = add ? 1 : -1;
    693 	for(int x = u; ; x = par[x]) {
    694 		tri &tX = nmp[x][Z];
    695 		tX.C += mul;
    696 		if(!tX.C) {
    697 			nmp[x].erase(Z);
    698 		} else {
    699 			tX.A += mul * dist(u, x);
    700 			tX.B += mul * dist(u, par[x]);
    701 		}
    702 		if(x == par[x]) break;
    703 	}
    704 }
    705 
    706 void upd(int u, bool add) {
    707 	if(add) {
    708 		updTree(u, add);
    709 		updAns(u, add);
    710 	} else {
    711 		updAns(u, add);
    712 		updTree(u, add);
    713 	} 
    714 }
    715 
    716 //=========================================MAIN============================================
    717 
    718 int main(){
    719 	
    720 	int m, q, ac;
    721 	scanf("%d %d %d %d", &n, &m, &q, &ac);
    722 
    723 	for(int i = 1; i <= n; ++i) {
    724 		scanf("%d", &V[i]);
    725 	}
    726 	
    727 	for(int i = 2; i <= n; ++i) {
    728 		int v;
    729 		scanf("%d", &v);
    730 		e[v].pb(i);
    731 		e[i].pb(v);
    732 	}
    733 
    734 	for(int i = 1; i <= m; ++i) {
    735 		scanf("%d", &CS[i]);
    736 	}
    737 
    738 	L[1] = 1;
    739 	getLevel(1);
    740 	prepAncestor();
    741 	decompose(1);
    742 	
    743 	for(int i = 1; i <= n; ++i) {
    744 		upd(i, true);
    745 	}
    746 
    747 	while(q--) {
    748 		int t;
    749 		scanf("%d", &t);
    750 		if(t == 1) {
    751 			int u, v;
    752 			scanf("%d %d", &u, &v);
    753 			upd(u, false);
    754 			V[u] = v; 
    755 			upd(u, true);
    756 		}
    757 		else if(t == 2) {
    758 			int v;
    759 			scanf("%d", &v);
    760 			long double ans = S[v] * T[v] - D[v] / 2;
    761 
    762 			ans *= 1LL * CS[v] * CS[v];
    763 
    764 			ans += 1LL * n * ac * ac;
    765 
    766 			
    767 			long long anst = 2LL * CS[v] * ac * S[v];
    768 			
    769 			ans -= anst;
    770 
    771 			cout << fixed << setprecision(12) << ans / n << "\n"; 
    772 		}
    773 	}
    774 }
    775 ```
    776 
    777 Do give your feedback here : <https://goo.gl/forms/xbsdMxnkA3XsG4092>. Would love to hear your feedback, since that would help us get better!