Submission #782226

#	Time	Username	Problem	Language	Result	Execution time	Memory
782226		amirhoseinfar1385	Sumtree (INOI20_sumtree)	C++17	10 / 100	599 ms	539200 KiB

Main

#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],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 upd(long long i,long long w){
		if(i==0)
		{
			return ;
		}
		//return ;
		if(i<0||i>=(1<<20)){
			return ;
		}
		if((i<<1)>=(1<<20)){
			seg[i]=w;
			return upd((i>>1),w);
		}
	//	return ;
		////cout<<i<<" "<<w<<" "<<seg[(i<<1)]<<" "<<seg[(i<<1)^1]<<"\n";
		if((seg[(i<<1)])==-1&&seg[(i<<1)^1]==-1){
			seg[i]=-1;
			return upd((i>>1),w);
		}
		//return ;
		if((seg[(i<<1)])==-1){
			seg[i]=seg[(i<<1)^1];
			return upd((i>>1),w);
		}
		if(seg[(i<<1)^1]==-1){
			seg[i]=seg[(i<<1)];
			return upd((i>>1),w);
		}
		seg[i]=1ll*seg[(i<<1)]*seg[(i<<1)^1]%mod;
		return upd((i>>1),w);
	}

}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(){	
	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){
	//cout<<"av: "<<i<<" "<<j<<"\n";
	if(i<0||j<0||i<j){
		return 0;
	}
	//cout<<"dov: "<<i<<" "<<j<<"\n";
	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++;
	//cout<<"wtf: "<<a<<" "<<b<<"\n";
	long long ret=c(b+a-1,a-1);	
	return ret;
}

void tof(){
	//cout<<"salam"<<endl;
	res.upd(stf[1].first+kaf,hes(n-1,val[1]));
	//cout<<"vas "<<n-1<<" "<<val[1]<<" "<<hes(n-1,val[1])<<endl;
	segbal.upd(1,0,kaf-1,stf[1].first+1,stf[1].second,1);
	//cout<<"akh"<<endl;
	link[1]=0;
}

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 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);
	//return ;
	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);
	//return ;
	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);
	//return ;
	//cout<<tedp<<" asd "<<val[pp]<<" "<<jamp<<" "<<ted<<" "<<fake<<"\n";
	res.upd(kaf+stf[pp].first,-1);
	//return ;
	if(kaf+stf[pp].first>=(1<<20)){
		return ;
	}
	res.upd(kaf+stf[pp].first,fake);
	//return ;
	fake=hes(ted-1,val[u]-jam);
	//cout<<ted<<" sec "<<val[u]<<" "<<jam<<"\n";
	res.upd(stf[u].first+kaf,fake);
}

void del(long long u){
	long long pp=segbal.get(stf[u].first+kaf).second;
	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);
	res.upd(kaf+stf[pp].first,-1);
	res.upd(kaf+stf[pp].first,fake);
	res.upd(stf[u].first+kaf,-1);
}

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);
	////cout<<"salam"<<endl;
	val[1]=k;
	tof();
	//cout<<"salam"<<endl;
	long long q;
	cin>>q;
	asd=1;
	cout<<res.seg[1]<<"\n";
	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";
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30