oj.uz

Submission #783984

# Submission time Handle Problem Language Result Execution time Memory
783984 2023-07-15T13:53:47 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
10 / 100
 3000 ms 570916 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;
}
 
void tof(){
	fres[stf[1].first]=hes(n-1,val[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 findp(int u,int av){
	if(u==av||val[u]==-1){
		return findp(par[u],av);
	}
	return u;
}

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 ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	segted.upd(kaf+stf[u].first,ted);
//	segbal.upd(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
	segjam.upd(kaf+stf[u].first,-jam+w);
	long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	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 ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	segted.upd(kaf+stf[u].first,-ted);
//	segbal.del(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
	segjam.upd(kaf+stf[u].first,+jam-wa[u]);
	long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	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";
}

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 299 ms 288488 KB Output is correct
2 Correct 301 ms 288516 KB Output is correct
3 Correct 284 ms 288464 KB Output is correct
4 Correct 281 ms 288584 KB Output is correct
5 Correct 266 ms 285776 KB Output is correct
6 Correct 195 ms 261856 KB Output is correct
7 Correct 190 ms 261652 KB Output is correct
8 Correct 205 ms 261696 KB Output is correct
9 Correct 295 ms 280600 KB Output is correct
10 Correct 300 ms 280388 KB Output is correct
11 Correct 293 ms 280592 KB Output is correct
12 Correct 292 ms 279620 KB Output is correct
13 Correct 270 ms 286800 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 191 ms 261440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 881 ms 570916 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 288652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 288488 KB Output is correct
2 Correct 301 ms 288516 KB Output is correct
3 Correct 284 ms 288464 KB Output is correct
4 Correct 281 ms 288584 KB Output is correct
5 Correct 266 ms 285776 KB Output is correct
6 Correct 195 ms 261856 KB Output is correct
7 Correct 190 ms 261652 KB Output is correct
8 Correct 205 ms 261696 KB Output is correct
9 Correct 295 ms 280600 KB Output is correct
10 Correct 300 ms 280388 KB Output is correct
11 Correct 293 ms 280592 KB Output is correct
12 Correct 292 ms 279620 KB Output is correct
13 Correct 270 ms 286800 KB Output is correct
14 Incorrect 191 ms 261440 KB Output isn't correct
15 Halted 0 ms 0 KB -