oj.uz

Submission #784062

# Submission time Handle Problem Language Result Execution time Memory
784062 2023-07-15T15:41:22 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
100 / 100
 1352 ms 348368 KB 
#include<bits/stdc++.h>
using namespace std;
long long n,k;
const long long maxn=200000+10,maxm=500000+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 144 ms 105164 KB Output is correct
2 Correct 152 ms 105164 KB Output is correct
3 Correct 144 ms 105088 KB Output is correct
4 Correct 142 ms 105168 KB Output is correct
5 Correct 117 ms 102348 KB Output is correct
6 Correct 43 ms 78664 KB Output is correct
7 Correct 42 ms 78432 KB Output is correct
8 Correct 41 ms 78384 KB Output is correct
9 Correct 155 ms 97232 KB Output is correct
10 Correct 155 ms 97228 KB Output is correct
11 Correct 160 ms 97204 KB Output is correct
12 Correct 145 ms 96232 KB Output is correct
13 Correct 137 ms 103348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 78224 KB Output is correct
2 Correct 43 ms 78252 KB Output is correct
3 Correct 41 ms 78232 KB Output is correct
4 Correct 45 ms 78264 KB Output is correct
5 Correct 42 ms 78328 KB Output is correct
6 Correct 47 ms 78588 KB Output is correct
7 Correct 43 ms 78540 KB Output is correct
8 Correct 43 ms 78556 KB Output is correct
9 Correct 45 ms 78680 KB Output is correct
10 Correct 46 ms 78812 KB Output is correct
11 Correct 47 ms 78872 KB Output is correct
12 Correct 43 ms 78908 KB Output is correct
13 Correct 46 ms 78884 KB Output is correct
14 Correct 48 ms 78860 KB Output is correct
15 Correct 49 ms 79208 KB Output is correct
16 Correct 45 ms 78736 KB Output is correct
17 Correct 53 ms 78848 KB Output is correct
18 Correct 47 ms 78748 KB Output is correct
19 Correct 46 ms 78680 KB Output is correct
20 Correct 44 ms 78576 KB Output is correct
21 Correct 43 ms 78540 KB Output is correct
22 Correct 40 ms 78364 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 115592 KB Output is correct
2 Correct 230 ms 122524 KB Output is correct
3 Correct 196 ms 117004 KB Output is correct
4 Correct 346 ms 134340 KB Output is correct
5 Correct 909 ms 195364 KB Output is correct
6 Correct 46 ms 79640 KB Output is correct
7 Correct 44 ms 78724 KB Output is correct
8 Correct 45 ms 79012 KB Output is correct
9 Correct 395 ms 113468 KB Output is correct
10 Correct 354 ms 111436 KB Output is correct
11 Correct 318 ms 110696 KB Output is correct
12 Correct 374 ms 111564 KB Output is correct
13 Correct 1076 ms 298176 KB Output is correct
14 Correct 975 ms 285720 KB Output is correct
15 Correct 1352 ms 348368 KB Output is correct
16 Correct 1296 ms 335928 KB Output is correct
17 Correct 976 ms 286012 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 107072 KB Output is correct
2 Correct 553 ms 107132 KB Output is correct
3 Correct 546 ms 107212 KB Output is correct
4 Correct 546 ms 107196 KB Output is correct
5 Correct 543 ms 105840 KB Output is correct
6 Correct 579 ms 107184 KB Output is correct
7 Correct 407 ms 93856 KB Output is correct
8 Correct 414 ms 93868 KB Output is correct
9 Correct 537 ms 107212 KB Output is correct
10 Correct 524 ms 107196 KB Output is correct
11 Correct 526 ms 107188 KB Output is correct
12 Correct 408 ms 93772 KB Output is correct
13 Correct 319 ms 89088 KB Output is correct
14 Correct 335 ms 91568 KB Output is correct
15 Correct 360 ms 92276 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 105164 KB Output is correct
2 Correct 152 ms 105164 KB Output is correct
3 Correct 144 ms 105088 KB Output is correct
4 Correct 142 ms 105168 KB Output is correct
5 Correct 117 ms 102348 KB Output is correct
6 Correct 43 ms 78664 KB Output is correct
7 Correct 42 ms 78432 KB Output is correct
8 Correct 41 ms 78384 KB Output is correct
9 Correct 155 ms 97232 KB Output is correct
10 Correct 155 ms 97228 KB Output is correct
11 Correct 160 ms 97204 KB Output is correct
12 Correct 145 ms 96232 KB Output is correct
13 Correct 137 ms 103348 KB Output is correct
14 Correct 40 ms 78224 KB Output is correct
15 Correct 43 ms 78252 KB Output is correct
16 Correct 41 ms 78232 KB Output is correct
17 Correct 45 ms 78264 KB Output is correct
18 Correct 42 ms 78328 KB Output is correct
19 Correct 47 ms 78588 KB Output is correct
20 Correct 43 ms 78540 KB Output is correct
21 Correct 43 ms 78556 KB Output is correct
22 Correct 45 ms 78680 KB Output is correct
23 Correct 46 ms 78812 KB Output is correct
24 Correct 47 ms 78872 KB Output is correct
25 Correct 43 ms 78908 KB Output is correct
26 Correct 46 ms 78884 KB Output is correct
27 Correct 48 ms 78860 KB Output is correct
28 Correct 49 ms 79208 KB Output is correct
29 Correct 45 ms 78736 KB Output is correct
30 Correct 53 ms 78848 KB Output is correct
31 Correct 47 ms 78748 KB Output is correct
32 Correct 46 ms 78680 KB Output is correct
33 Correct 44 ms 78576 KB Output is correct
34 Correct 43 ms 78540 KB Output is correct
35 Correct 40 ms 78364 KB Output is correct
36 Correct 177 ms 115592 KB Output is correct
37 Correct 230 ms 122524 KB Output is correct
38 Correct 196 ms 117004 KB Output is correct
39 Correct 346 ms 134340 KB Output is correct
40 Correct 909 ms 195364 KB Output is correct
41 Correct 46 ms 79640 KB Output is correct
42 Correct 44 ms 78724 KB Output is correct
43 Correct 45 ms 79012 KB Output is correct
44 Correct 395 ms 113468 KB Output is correct
45 Correct 354 ms 111436 KB Output is correct
46 Correct 318 ms 110696 KB Output is correct
47 Correct 374 ms 111564 KB Output is correct
48 Correct 1076 ms 298176 KB Output is correct
49 Correct 975 ms 285720 KB Output is correct
50 Correct 1352 ms 348368 KB Output is correct
51 Correct 1296 ms 335928 KB Output is correct
52 Correct 976 ms 286012 KB Output is correct
53 Correct 539 ms 107072 KB Output is correct
54 Correct 553 ms 107132 KB Output is correct
55 Correct 546 ms 107212 KB Output is correct
56 Correct 546 ms 107196 KB Output is correct
57 Correct 543 ms 105840 KB Output is correct
58 Correct 579 ms 107184 KB Output is correct
59 Correct 407 ms 93856 KB Output is correct
60 Correct 414 ms 93868 KB Output is correct
61 Correct 537 ms 107212 KB Output is correct
62 Correct 524 ms 107196 KB Output is correct
63 Correct 526 ms 107188 KB Output is correct
64 Correct 408 ms 93772 KB Output is correct
65 Correct 319 ms 89088 KB Output is correct
66 Correct 335 ms 91568 KB Output is correct
67 Correct 360 ms 92276 KB Output is correct
68 Correct 42 ms 78208 KB Output is correct
69 Correct 43 ms 78240 KB Output is correct
70 Correct 616 ms 115196 KB Output is correct
71 Correct 607 ms 115332 KB Output is correct
72 Correct 633 ms 115128 KB Output is correct
73 Correct 673 ms 115192 KB Output is correct
74 Correct 759 ms 115720 KB Output is correct
75 Correct 709 ms 111824 KB Output is correct
76 Correct 557 ms 107184 KB Output is correct
77 Correct 647 ms 107924 KB Output is correct
78 Correct 649 ms 109636 KB Output is correct
79 Correct 623 ms 111160 KB Output is correct
80 Correct 766 ms 110348 KB Output is correct
81 Correct 759 ms 111416 KB Output is correct
82 Correct 418 ms 100700 KB Output is correct
83 Correct 429 ms 107128 KB Output is correct
84 Correct 456 ms 106568 KB Output is correct
85 Correct 439 ms 106676 KB Output is correct