Submission #635988

#	Time	Username	Problem	Language	Result	Execution time	Memory
635988		amirhoseinfar1385	Sumtree (INOI20_sumtree)	C++17	10 / 100	520 ms	125480 KiB

Main

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long countz,tag,res,ftag;
	set<pair<long long ,long long>>mn;
	node(){
		countz=res=1;
		tag=0;
	};
};
vector<long long>high;
long long mod=1e9+7;
vector<long long>fact,revfact;
long long n,r;
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)==1){
		p=1ll*m*p;
		p%=mod;
	}
	return p;
}
vector<long long>st;
vector<pair<long long ,long long>>stf;
vector<vector<long long>>adj;
long long rishe=1;
node seg[(1<<20)];

void build(long long i){
	if((i<<1)>=(1<<20)){
		return ;
	}
	build((i<<1));
	build(((i<<1)^1));
	seg[i].countz=seg[(i<<1)].countz+seg[((i<<1)^1)].countz;
}

void aval(long long u=rishe,long long para=0,long long len=0){
	high[u]=len;
	st.push_back(u);
	stf[u].first=st.size()-1;
	for(auto x:adj[u]){
		if(x!=para){
			aval(x,u,len+1);
		}
	}
	stf[u].second=st.size()-1;
}


long long solvecz(long long i,long long nl,long long nr,long long tl,long long tr){
	if(nl>tr||nr<tl){
		return 0;
	}
	if(nl>=tl&&nr<=tr){
	//	cout<<nl<<" asd "<<nr<<" "<<seg[i].countz<<"\n";
		return seg[i].countz;
	}
	long long m=((nl+nr)>>1);
	long long d=solvecz((i<<1),nl,m,tl,tr);
	d+=solvecz(((i<<1)^1),m+1,nr,tl,tr);
	return d;
}

long long solvest(long long i,long long nl,long long nr,long long tl,long long tr){
	if(nl>tr||nr<tl){
		return 0;
	}
	if(nl>=tl&&nr<=tr){
	//	cout<<nl<<" asd "<<nr<<" "<<seg[i].tag<<"\n";
		return seg[i].tag;
	}
	long long m=((nl+nr)>>1);
	long long d=solvest((i<<1),nl,m,tl,tr);
	d+=solvest(((i<<1)^1),m+1,nr,tl,tr);
	return d;
}

void upmn(long long i,long long nl,long long nr,long long tl,long long tr,long long u){
	if(nl>tr||nr<tl){
		return ;
	}
	if(nl>=tl&&nr<=tr){
		seg[i].mn.insert(make_pair(-high[u],u));
		return ;
	}
	long long m=((nl+nr)>>1);
	upmn((i<<1),nl,m,tl,tr,u);
	upmn(((i<<1)^1),m+1,nr,tl,tr,u);
	return ;
}

void upd(long long u){
	if(u==0){
		return ;
	}
	seg[u].res=seg[(u<<1)].res*seg[((u<<1)^1)].res;
	seg[u].res%=mod;
	seg[u].countz=seg[(u<<1)].countz+seg[((u<<1)^1)].countz;
	seg[u].tag=seg[(u<<1)].tag+seg[((u<<1)^1)].tag;
	return upd((u>>1));
}

long long solvepar(long long u){
	if(u==0){
		return -1;
	}
	long long x=solvepar((u>>1));
	if(x==-1){
		if(seg[u].mn.size()==0){
			return -1;
		}
		pair<long long,long long> y=*(seg[u].mn.begin());
		return y.second;
	}
	else{
		if(seg[u].mn.size()==0){
			return x;
		}
		pair<long long,long long> y=*(seg[u].mn.begin());
		if(high[x]>-y.first){
			return x;
		}
		else{
			return y.second;
		}
	}
}

void update(long long u,long long no,long long c=0){
	if(no==1){
		seg[(1<<19)+stf[u].first].ftag=c;
		if(stf[u].first==stf[u].second){
			seg[(1<<19)+stf[u].first].tag=c;
			seg[(1<<19)+stf[u].first].res=1;
			seg[(1<<19)+stf[u].first].countz=0;
		}
		else{
			upmn(1,0,(1<<19)-1,stf[u].first+1,stf[u].second,u);
			seg[(1<<19)+stf[u].first].tag=c;
			seg[(1<<19)+stf[u].first].countz=-solvecz(1,0,(1<<19)-1,stf[u].first+1,stf[u].second);
			long long x=solvest(1,0,(1<<19)-1,stf[u].first+1,stf[u].second);
			if(x>c){
				seg[(1<<19)+stf[u].first].res=0;
			}
			else{
				seg[(1<<19)+stf[u].first].res=fact[c-x+-seg[(1<<19)+stf[u].first].countz];
				seg[(1<<19)+stf[u].first].res*=revfact[-seg[(1<<19)+stf[u].first].countz];
				seg[(1<<19)+stf[u].first].res%=mod;
				seg[(1<<19)+stf[u].first].res*=revfact[c-x];
				seg[(1<<19)+stf[u].first].res%=mod;
			}
	//		cout<<c<<" "<<x<<" "<<seg[(1<<19)+stf[u].first].countz<<"\n";
		}	
		long long fu=stf[u].first,ffu=u;
		fu+=(1<<19);
		fu=(fu>>1);
		upd(fu);
		fu=stf[u].first;
		fu+=(1<<19);
		u=solvepar(fu);
		fu=ffu;
		if(u==-1){
			return ;
		}
		seg[(1<<19)+stf[u].first].tag-=seg[(1<<19)+stf[fu].first].tag;
		c=seg[(1<<19)+stf[u].first].ftag;
	//	cout<<" s "<<u<<"\n";
		if(stf[u].first==stf[u].second){
			seg[(1<<19)+stf[u].first].res=1;
			seg[(1<<19)+stf[u].first].countz=0;
		}
		else{
			seg[(1<<19)+stf[u].first].countz=-solvecz(1,0,(1<<19)-1,stf[u].first+1,stf[u].second);
			long long x=solvest(1,0,(1<<19)-1,stf[u].first+1,stf[u].second);
			if(x>c){
				seg[(1<<19)+stf[u].first].res=0;
			//	cout<<c<<" "<<x<<"\n";
			}
			else{
				seg[(1<<19)+stf[u].first].res=fact[c-x+-seg[(1<<19)+stf[u].first].countz];
				seg[(1<<19)+stf[u].first].res*=revfact[-seg[(1<<19)+stf[u].first].countz];
				seg[(1<<19)+stf[u].first].res%=mod;
				seg[(1<<19)+stf[u].first].res*=revfact[c-x];
				seg[(1<<19)+stf[u].first].res%=mod;
			}
	//		cout<<c<<" "<<x<<" "<<seg[(1<<19)+stf[u].first].countz<<"\n";
		}	
		fu=stf[u].first;
		fu+=(1<<19);
		fu=(fu>>1);
		upd(fu);
	}
	else{

	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	fact.resize(1e6);
	revfact.resize(1e6);
	fact[0]=revfact[0]=1;
	for(int i=1;i<=5e5;i++){
		fact[i]=fact[i-1]*i;
		fact[i]%=mod;
		revfact[i]=mypow(fact[i],mod-2);
	}
	cin>>n>>r;
	adj.resize(n+1);
	high.resize(n+1);
	stf.resize(n+1);
	for(int i=0;i<n-1;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	build(1);
	aval();
	update(1,1,r);
	long long q;
	cin>>q;
	cout<<seg[1].res<<"\n";
	for(int i=0;i<q;i++){
		long long u;
		cin>>u;
		if(u==1){
			long long v,e;
			cin>>v>>e;
			update(v,1,e);
		}
		else{

		}
		cout<<seg[1].res<<"\n";
	}
}

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