oj.uz

Submission #784057

# Submission time Handle Problem Language Result Execution time Memory
784057 2023-07-15T15:36:04 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
100 / 100
 1494 ms 536968 KB 
#include<bits/stdc++.h>
using namespace std;
long long n,k;
const long long maxn=2000000+10,maxm=5000000+10;
vector<long long>adj[maxn],child[maxn];
long long par[maxn],val[maxn],link[maxn],fres[maxn],wa[maxn],cnt[maxn],asd,timea=0,high[maxn],fact[maxm],revfact[maxm],mod=1e9+7;
pair<long long,long long>stf[maxn];
 
long long kaf=(1<<19);
 
struct segment{
	set<pair<long long,long long>>seg[(1<<20)];
	pair<long long,long long> get(long long i){
		if(i==0){
			return make_pair(0,0);
		}
		if((long long)seg[i].size()==0){
			return get((i>>1));
		}
		auto x=*seg[i].rbegin();
		return max(get((i>>1)),x);
	}
	void del(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].erase(make_pair(high[w],w));
			return ;
		}
		long long m=(l+r)>>1;
		del((i<<1),l,m,tl,tr,w);
		del((i<<1)^1,m+1,r,tl,tr,w);
	}
 
	void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].insert(make_pair(high[w],w));
			return ;
		}
		long long m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
	}
}segbal;
 
struct segjam{
	long long seg[(1<<20)];
	long long pors(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		long long m=(l+r)>>1;
		long long ret=pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
		return ret;
	}
	void upd(long long i,long long w){
		if(i==0){
			return ;
		}
		seg[i]+=w;
		upd((i>>1),w);
	}
}segjam,segted;
 
struct segres{
	long long seg[(1<<20)];
	segres(){
		for(long long i=kaf;i<(1<<20);i++){
			seg[i]=-1;
		}
		for(long long i=1;i<kaf;i++){
			seg[i]=-1;
		}
	}
	void calc(int i){
		if(seg[(i<<1)]==-1&&seg[(i<<1)^1]==-1){
			seg[i]=-1;
			return ;
		}
		if(seg[(i<<1)]==-1){
			seg[i]=seg[(i<<1)^1];
			return ;
		}
		if(seg[(i<<1)^1]==-1){
			seg[i]=seg[(i<<1)];
			return ;
		}
		seg[i]=1ll*seg[(i<<1)^1]*seg[(i<<1)]%mod;
		return ;
	}
 
	void upd(int i,int l,int r,int tl,int tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			w%=mod;
			seg[i]=w;
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
	}
 
}res;
 
long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}
 
void aval(){	
	for(int i=0;i<maxn;i++){
		fres[i]=-1;
		val[i]=-1;
	}
	fact[0]=1;
	for(long long i=1;i<maxm;i++){
		fact[i]=1ll*fact[i-1]*i%mod;
	}
	revfact[maxm-1]=mypow(fact[maxm-1],mod-2);
	for(long long i=maxm-2;i>=0;i--){
		revfact[i]=1ll*revfact[i+1]*(i+1)%mod;
	}
}
 
long long c(long long i,long long j){
	if(i<0||j<0||i<j){
		return 0;
	}
	long long ret=1ll*fact[i]*revfact[j]%mod*revfact[i-j]%mod;
	return ret;
}
 
void dfs(long long u,long long para=0){
	cnt[u]=1;
	high[u]=high[para]+1;
	timea++;
	stf[u].first=timea;
	par[u]=para;
	for(auto x:adj[u]){
		if(x!=para){
			child[u].push_back(x);
			dfs(x,u);
			cnt[u]+=cnt[x];
		}
	}
	stf[u].second=timea;
}
 
long long hes(long long a,long long b){
	a++;
	long long ret=c(b+a-1,a-1);	
	return ret;
}

int findp(int u,int av){
	if(u==av||val[u]==-1){
		return findp(par[u],av);
	}
	return u;
}

long long porsjam(int u,int av){
	long long ret=0;
	if(u!=av&&val[u]!=-1){
		ret+=val[u];
		return ret;
	}
	for(auto x:child[u]){
		ret+=porsjam(x,av);
	}
	return ret;
}

long long porsted(int u,int av){
	long long ret=0;
	if(u!=av&&val[u]!=-1){
		return ret;
	}
	for(auto x:child[u]){
		ret+=porsted(x,av);
	}
	ret++;
	return ret;
}

void upd(long long u,long long w){
	wa[u]=w;
	val[u]=w;
	long long pp=segbal.get(stf[u].first+kaf).second;
//	long long pp=findp(u,u);
	long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
//	long long jam=porsjam(u,u);
	long long ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
//	long long ted=porsted(u,u);
	segted.upd(kaf+stf[u].first,ted);
	segted.upd(kaf+stf[pp].first,-ted);
	segbal.upd(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
	segjam.upd(kaf+stf[u].first,-jam+w);
	segjam.upd(kaf+stf[pp].first,+jam-w);
	long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
//	long long jamp=porsjam(pp,pp);
	long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
//	long long tedp=porsted(pp,pp);
	long long fake=hes(tedp-1,val[pp]-jamp);
//	fres[stf[pp].first]=fake;
//	cout<<u<<" "<<pp<<" "<<jamp<<" "<<val[pp]<<" "<<tedp<<"\n";
	res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,fake);
	fake=hes(ted-1,val[u]-jam);
//	fres[stf[u].first]=fake;
	res.upd(1,0,kaf-1,stf[u].first,stf[u].first,fake);
}
 
void del(long long u){
	long long pp=segbal.get(stf[u].first+kaf).second;
//	long long pp=findp(u,u);
	long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
//	long long jam=porsjam(u,u);
	long long ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
//	long long ted=porsted(u,u);
	segted.upd(kaf+stf[u].first,-ted);
	segted.upd(kaf+stf[pp].first,+ted);
	segbal.del(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
	segjam.upd(kaf+stf[u].first,+jam-val[u]);
	segjam.upd(kaf+stf[pp].first,-jam+val[u]);
	val[u]=-1;
	long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
//	long long jamp=porsjam(pp,pp);
	long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
//	long long tedp=porsted(pp,pp);
	long long fake=hes(tedp-1,val[pp]-jamp);
	fres[stf[pp].first]=fake;
	fres[stf[u].first]=-1;
//	res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,-1);
	res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,fake);
	res.upd(1,0,kaf-1,stf[u].first,stf[u].first,-1);
//	val[u]=-1;
}
 
void calres(){
	long long ret=1;
	for(int i=stf[1].first;i<=stf[1].second;i++){
//		cout<<i<<" asd "<<fres[i]<<"\n";
		if(fres[i]==-1){
			continue;
		}
		ret*=fres[i];
		ret%=mod;
	}
	cout<<ret<<"\n";
}

void tof(){
	//cout<<porsted(1,1)<<" "<<porsjam(1,1)<<"\n";
	fres[stf[1].first]=hes(porsted(1,1)-1,val[1]-porsjam(1,1));
	res.upd(1,0,kaf-1,stf[1].first,stf[1].first,hes(n-1,val[1]));
	segbal.upd(1,0,kaf-1,stf[1].first+1,stf[1].second,1);
	link[1]=0;
}
 

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	aval();
	cin>>n>>k;
	for(long long i=0;i<n-1;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1);
//	segjam.upd(stf[1].first+kaf,k);
	val[1]=k;
	tof();
	long long q;
	cin>>q;
	asd=1;
	cout<<res.seg[1]<<"\n";
//	calres();
	for(;asd<=q;asd++){
		long long qq;
		cin>>qq;
		if(qq==1){
			long long u,w;
			cin>>u>>w;
			upd(u,w);
		}
		else{
			long long u;
			cin>>u;
			del(u);
		}
		cout<<res.seg[1]<<"\n";
//		calres();
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 288320 KB Output is correct
2 Correct 295 ms 288348 KB Output is correct
3 Correct 313 ms 288292 KB Output is correct
4 Correct 331 ms 288380 KB Output is correct
5 Correct 264 ms 285524 KB Output is correct
6 Correct 192 ms 261852 KB Output is correct
7 Correct 191 ms 261508 KB Output is correct
8 Correct 190 ms 261600 KB Output is correct
9 Correct 312 ms 280352 KB Output is correct
10 Correct 299 ms 280244 KB Output is correct
11 Correct 303 ms 280268 KB Output is correct
12 Correct 302 ms 279348 KB Output is correct
13 Correct 283 ms 286536 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 261408 KB Output is correct
2 Correct 195 ms 261424 KB Output is correct
3 Correct 203 ms 261380 KB Output is correct
4 Correct 190 ms 261388 KB Output is correct
5 Correct 199 ms 261552 KB Output is correct
6 Correct 194 ms 261700 KB Output is correct
7 Correct 196 ms 261792 KB Output is correct
8 Correct 195 ms 261708 KB Output is correct
9 Correct 194 ms 261920 KB Output is correct
10 Correct 198 ms 262048 KB Output is correct
11 Correct 198 ms 262148 KB Output is correct
12 Correct 191 ms 262076 KB Output is correct
13 Correct 204 ms 262100 KB Output is correct
14 Correct 198 ms 262092 KB Output is correct
15 Correct 207 ms 262588 KB Output is correct
16 Correct 192 ms 261884 KB Output is correct
17 Correct 205 ms 262092 KB Output is correct
18 Correct 202 ms 261972 KB Output is correct
19 Correct 195 ms 261860 KB Output is correct
20 Correct 190 ms 261708 KB Output is correct
21 Correct 199 ms 261708 KB Output is correct
22 Correct 196 ms 261396 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 298868 KB Output is correct
2 Correct 411 ms 305720 KB Output is correct
3 Correct 334 ms 302472 KB Output is correct
4 Correct 495 ms 320504 KB Output is correct
5 Correct 1092 ms 382444 KB Output is correct
6 Correct 210 ms 262844 KB Output is correct
7 Correct 197 ms 261904 KB Output is correct
8 Correct 199 ms 262220 KB Output is correct
9 Correct 579 ms 300092 KB Output is correct
10 Correct 497 ms 297844 KB Output is correct
11 Correct 479 ms 297016 KB Output is correct
12 Correct 532 ms 298524 KB Output is correct
13 Correct 1263 ms 486936 KB Output is correct
14 Correct 1118 ms 474328 KB Output is correct
15 Correct 1494 ms 536968 KB Output is correct
16 Correct 1439 ms 524448 KB Output is correct
17 Correct 1163 ms 474252 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 290280 KB Output is correct
2 Correct 688 ms 294564 KB Output is correct
3 Correct 694 ms 294800 KB Output is correct
4 Correct 674 ms 294708 KB Output is correct
5 Correct 703 ms 293088 KB Output is correct
6 Correct 692 ms 294692 KB Output is correct
7 Correct 552 ms 279788 KB Output is correct
8 Correct 566 ms 279864 KB Output is correct
9 Correct 711 ms 294732 KB Output is correct
10 Correct 662 ms 294848 KB Output is correct
11 Correct 724 ms 294900 KB Output is correct
12 Correct 600 ms 279916 KB Output is correct
13 Correct 470 ms 275364 KB Output is correct
14 Correct 496 ms 278108 KB Output is correct
15 Correct 493 ms 278552 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 288320 KB Output is correct
2 Correct 295 ms 288348 KB Output is correct
3 Correct 313 ms 288292 KB Output is correct
4 Correct 331 ms 288380 KB Output is correct
5 Correct 264 ms 285524 KB Output is correct
6 Correct 192 ms 261852 KB Output is correct
7 Correct 191 ms 261508 KB Output is correct
8 Correct 190 ms 261600 KB Output is correct
9 Correct 312 ms 280352 KB Output is correct
10 Correct 299 ms 280244 KB Output is correct
11 Correct 303 ms 280268 KB Output is correct
12 Correct 302 ms 279348 KB Output is correct
13 Correct 283 ms 286536 KB Output is correct
14 Correct 196 ms 261408 KB Output is correct
15 Correct 195 ms 261424 KB Output is correct
16 Correct 203 ms 261380 KB Output is correct
17 Correct 190 ms 261388 KB Output is correct
18 Correct 199 ms 261552 KB Output is correct
19 Correct 194 ms 261700 KB Output is correct
20 Correct 196 ms 261792 KB Output is correct
21 Correct 195 ms 261708 KB Output is correct
22 Correct 194 ms 261920 KB Output is correct
23 Correct 198 ms 262048 KB Output is correct
24 Correct 198 ms 262148 KB Output is correct
25 Correct 191 ms 262076 KB Output is correct
26 Correct 204 ms 262100 KB Output is correct
27 Correct 198 ms 262092 KB Output is correct
28 Correct 207 ms 262588 KB Output is correct
29 Correct 192 ms 261884 KB Output is correct
30 Correct 205 ms 262092 KB Output is correct
31 Correct 202 ms 261972 KB Output is correct
32 Correct 195 ms 261860 KB Output is correct
33 Correct 190 ms 261708 KB Output is correct
34 Correct 199 ms 261708 KB Output is correct
35 Correct 196 ms 261396 KB Output is correct
36 Correct 337 ms 298868 KB Output is correct
37 Correct 411 ms 305720 KB Output is correct
38 Correct 334 ms 302472 KB Output is correct
39 Correct 495 ms 320504 KB Output is correct
40 Correct 1092 ms 382444 KB Output is correct
41 Correct 210 ms 262844 KB Output is correct
42 Correct 197 ms 261904 KB Output is correct
43 Correct 199 ms 262220 KB Output is correct
44 Correct 579 ms 300092 KB Output is correct
45 Correct 497 ms 297844 KB Output is correct
46 Correct 479 ms 297016 KB Output is correct
47 Correct 532 ms 298524 KB Output is correct
48 Correct 1263 ms 486936 KB Output is correct
49 Correct 1118 ms 474328 KB Output is correct
50 Correct 1494 ms 536968 KB Output is correct
51 Correct 1439 ms 524448 KB Output is correct
52 Correct 1163 ms 474252 KB Output is correct
53 Correct 713 ms 290280 KB Output is correct
54 Correct 688 ms 294564 KB Output is correct
55 Correct 694 ms 294800 KB Output is correct
56 Correct 674 ms 294708 KB Output is correct
57 Correct 703 ms 293088 KB Output is correct
58 Correct 692 ms 294692 KB Output is correct
59 Correct 552 ms 279788 KB Output is correct
60 Correct 566 ms 279864 KB Output is correct
61 Correct 711 ms 294732 KB Output is correct
62 Correct 662 ms 294848 KB Output is correct
63 Correct 724 ms 294900 KB Output is correct
64 Correct 600 ms 279916 KB Output is correct
65 Correct 470 ms 275364 KB Output is correct
66 Correct 496 ms 278108 KB Output is correct
67 Correct 493 ms 278552 KB Output is correct
68 Correct 189 ms 261408 KB Output is correct
69 Correct 189 ms 261324 KB Output is correct
70 Correct 747 ms 302984 KB Output is correct
71 Correct 805 ms 302920 KB Output is correct
72 Correct 755 ms 302996 KB Output is correct
73 Correct 759 ms 302948 KB Output is correct
74 Correct 913 ms 303352 KB Output is correct
75 Correct 841 ms 299512 KB Output is correct
76 Correct 679 ms 294832 KB Output is correct
77 Correct 730 ms 295396 KB Output is correct
78 Correct 751 ms 297056 KB Output is correct
79 Correct 733 ms 298772 KB Output is correct
80 Correct 820 ms 297784 KB Output is correct
81 Correct 832 ms 298968 KB Output is correct
82 Correct 544 ms 288524 KB Output is correct
83 Correct 565 ms 294940 KB Output is correct
84 Correct 605 ms 294312 KB Output is correct
85 Correct 567 ms 294348 KB Output is correct