oj.uz

Submission #784071

# Submission time Handle Problem Language Result Execution time Memory
784071 2023-07-15T15:45:47 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
100 / 100
 1275 ms 279104 KB 
#include<bits/stdc++.h>
using namespace std;
int n,k;
const int maxn=200000+10,maxm=500000+10;
vector<int>adj[maxn],child[maxn];
int 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<int,int>stf[maxn];
int kaf=(1<<19);
 
struct segment{
	set<pair<int,int>>seg[(1<<20)];
	pair<int,int> get(int 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(int i,int l,int r,int tl,int tr,int 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 ;
		}
		int m=(l+r)>>1;
		del((i<<1),l,m,tl,tr,w);
		del((i<<1)^1,m+1,r,tl,tr,w);
	}
 
	void upd(int i,int l,int r,int tl,int tr,int 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 ;
		}
		int 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{
	int seg[(1<<20)];
	int pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		int m=(l+r)>>1;
		int ret=pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
		return ret;
	}
	void upd(int i,int 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 136 ms 94544 KB Output is correct
2 Correct 139 ms 94608 KB Output is correct
3 Correct 153 ms 94500 KB Output is correct
4 Correct 154 ms 94712 KB Output is correct
5 Correct 120 ms 92908 KB Output is correct
6 Correct 42 ms 73040 KB Output is correct
7 Correct 43 ms 72864 KB Output is correct
8 Correct 47 ms 72908 KB Output is correct
9 Correct 144 ms 86220 KB Output is correct
10 Correct 150 ms 86280 KB Output is correct
11 Correct 152 ms 86300 KB Output is correct
12 Correct 134 ms 85548 KB Output is correct
13 Correct 128 ms 93288 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 72652 KB Output is correct
2 Correct 42 ms 72664 KB Output is correct
3 Correct 42 ms 72748 KB Output is correct
4 Correct 41 ms 72788 KB Output is correct
5 Correct 42 ms 72780 KB Output is correct
6 Correct 44 ms 72968 KB Output is correct
7 Correct 44 ms 72992 KB Output is correct
8 Correct 44 ms 72932 KB Output is correct
9 Correct 46 ms 73036 KB Output is correct
10 Correct 49 ms 73216 KB Output is correct
11 Correct 48 ms 73280 KB Output is correct
12 Correct 41 ms 73108 KB Output is correct
13 Correct 48 ms 73228 KB Output is correct
14 Correct 46 ms 73168 KB Output is correct
15 Correct 50 ms 73564 KB Output is correct
16 Correct 46 ms 73012 KB Output is correct
17 Correct 46 ms 73132 KB Output is correct
18 Correct 47 ms 73120 KB Output is correct
19 Correct 46 ms 73028 KB Output is correct
20 Correct 42 ms 72892 KB Output is correct
21 Correct 42 ms 72900 KB Output is correct
22 Correct 41 ms 72804 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 100260 KB Output is correct
2 Correct 215 ms 105472 KB Output is correct
3 Correct 169 ms 101340 KB Output is correct
4 Correct 314 ms 114632 KB Output is correct
5 Correct 874 ms 161100 KB Output is correct
6 Correct 48 ms 73788 KB Output is correct
7 Correct 48 ms 73060 KB Output is correct
8 Correct 45 ms 73392 KB Output is correct
9 Correct 356 ms 96712 KB Output is correct
10 Correct 326 ms 95324 KB Output is correct
11 Correct 318 ms 94576 KB Output is correct
12 Correct 388 ms 95204 KB Output is correct
13 Correct 1020 ms 241328 KB Output is correct
14 Correct 933 ms 232012 KB Output is correct
15 Correct 1275 ms 279104 KB Output is correct
16 Correct 1210 ms 269512 KB Output is correct
17 Correct 937 ms 231932 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 92336 KB Output is correct
2 Correct 532 ms 92132 KB Output is correct
3 Correct 530 ms 92224 KB Output is correct
4 Correct 531 ms 92368 KB Output is correct
5 Correct 494 ms 91348 KB Output is correct
6 Correct 519 ms 92240 KB Output is correct
7 Correct 417 ms 83532 KB Output is correct
8 Correct 412 ms 83500 KB Output is correct
9 Correct 525 ms 92288 KB Output is correct
10 Correct 485 ms 92212 KB Output is correct
11 Correct 484 ms 92224 KB Output is correct
12 Correct 402 ms 83484 KB Output is correct
13 Correct 298 ms 80556 KB Output is correct
14 Correct 347 ms 81968 KB Output is correct
15 Correct 366 ms 81884 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 94544 KB Output is correct
2 Correct 139 ms 94608 KB Output is correct
3 Correct 153 ms 94500 KB Output is correct
4 Correct 154 ms 94712 KB Output is correct
5 Correct 120 ms 92908 KB Output is correct
6 Correct 42 ms 73040 KB Output is correct
7 Correct 43 ms 72864 KB Output is correct
8 Correct 47 ms 72908 KB Output is correct
9 Correct 144 ms 86220 KB Output is correct
10 Correct 150 ms 86280 KB Output is correct
11 Correct 152 ms 86300 KB Output is correct
12 Correct 134 ms 85548 KB Output is correct
13 Correct 128 ms 93288 KB Output is correct
14 Correct 45 ms 72652 KB Output is correct
15 Correct 42 ms 72664 KB Output is correct
16 Correct 42 ms 72748 KB Output is correct
17 Correct 41 ms 72788 KB Output is correct
18 Correct 42 ms 72780 KB Output is correct
19 Correct 44 ms 72968 KB Output is correct
20 Correct 44 ms 72992 KB Output is correct
21 Correct 44 ms 72932 KB Output is correct
22 Correct 46 ms 73036 KB Output is correct
23 Correct 49 ms 73216 KB Output is correct
24 Correct 48 ms 73280 KB Output is correct
25 Correct 41 ms 73108 KB Output is correct
26 Correct 48 ms 73228 KB Output is correct
27 Correct 46 ms 73168 KB Output is correct
28 Correct 50 ms 73564 KB Output is correct
29 Correct 46 ms 73012 KB Output is correct
30 Correct 46 ms 73132 KB Output is correct
31 Correct 47 ms 73120 KB Output is correct
32 Correct 46 ms 73028 KB Output is correct
33 Correct 42 ms 72892 KB Output is correct
34 Correct 42 ms 72900 KB Output is correct
35 Correct 41 ms 72804 KB Output is correct
36 Correct 167 ms 100260 KB Output is correct
37 Correct 215 ms 105472 KB Output is correct
38 Correct 169 ms 101340 KB Output is correct
39 Correct 314 ms 114632 KB Output is correct
40 Correct 874 ms 161100 KB Output is correct
41 Correct 48 ms 73788 KB Output is correct
42 Correct 48 ms 73060 KB Output is correct
43 Correct 45 ms 73392 KB Output is correct
44 Correct 356 ms 96712 KB Output is correct
45 Correct 326 ms 95324 KB Output is correct
46 Correct 318 ms 94576 KB Output is correct
47 Correct 388 ms 95204 KB Output is correct
48 Correct 1020 ms 241328 KB Output is correct
49 Correct 933 ms 232012 KB Output is correct
50 Correct 1275 ms 279104 KB Output is correct
51 Correct 1210 ms 269512 KB Output is correct
52 Correct 937 ms 231932 KB Output is correct
53 Correct 544 ms 92336 KB Output is correct
54 Correct 532 ms 92132 KB Output is correct
55 Correct 530 ms 92224 KB Output is correct
56 Correct 531 ms 92368 KB Output is correct
57 Correct 494 ms 91348 KB Output is correct
58 Correct 519 ms 92240 KB Output is correct
59 Correct 417 ms 83532 KB Output is correct
60 Correct 412 ms 83500 KB Output is correct
61 Correct 525 ms 92288 KB Output is correct
62 Correct 485 ms 92212 KB Output is correct
63 Correct 484 ms 92224 KB Output is correct
64 Correct 402 ms 83484 KB Output is correct
65 Correct 298 ms 80556 KB Output is correct
66 Correct 347 ms 81968 KB Output is correct
67 Correct 366 ms 81884 KB Output is correct
68 Correct 43 ms 72696 KB Output is correct
69 Correct 43 ms 72712 KB Output is correct
70 Correct 589 ms 100596 KB Output is correct
71 Correct 591 ms 100804 KB Output is correct
72 Correct 600 ms 100632 KB Output is correct
73 Correct 581 ms 100608 KB Output is correct
74 Correct 734 ms 101024 KB Output is correct
75 Correct 712 ms 97632 KB Output is correct
76 Correct 503 ms 92280 KB Output is correct
77 Correct 554 ms 92780 KB Output is correct
78 Correct 566 ms 93800 KB Output is correct
79 Correct 590 ms 96284 KB Output is correct
80 Correct 773 ms 95872 KB Output is correct
81 Correct 751 ms 96616 KB Output is correct
82 Correct 469 ms 88956 KB Output is correct
83 Correct 414 ms 96380 KB Output is correct
84 Correct 562 ms 95716 KB Output is correct
85 Correct 489 ms 95816 KB Output is correct