Submission #783973

#	Time	Username	Problem	Language	Result	Execution time	Memory
783973		amirhoseinfar1385	Sumtree (INOI20_sumtree)	C++17	30 / 100	3060 ms	52132 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
vector<int>adj[maxn];
int n,q,mod=1e9+7,fact[maxn],revfact[maxn],val[maxn];
long long res=0;

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<maxn;i++){
		fact[i]=1ll*fact[i-1]*i%mod;
	}
	revfact[maxn-1]=mypow(fact[maxn-1],mod-2);
	for(long long i=maxn-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;
}

long long hes(long long a,long long b){
	a++;
	long long ret=c(b+a-1,a-1);	
	return ret;
}
long long ted[maxn],jam[maxn];

void solve(int u=1,int par=0){
	ted[u]=jam[u]=0;
	for(auto x:adj[u]){
		if(x!=par){
			solve(x,u);
			ted[u]+=ted[x];
			jam[u]+=jam[x];
		}
	}
	//cout<<u<<" "<<val[u]<<" "<<ted[u]<<" "<<jam[u]<<"\n";
	if(val[u]==-1){
		ted[u]++;
	}
	else{
		res*=hes(ted[u],val[u]-jam[u]);
		res%=mod;
		ted[u]=0;
		jam[u]=val[u];
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	aval();
	int k;
	cin>>n;
	cin>>k;
	val[1]=k;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=2;i<=n;i++){
		val[i]=-1;
	}
	res=1;
	solve();
	cout<<res<<"\n";
	cin>>q;
	for(int i=0;i<q;i++){
		int qq;
		cin>>qq;
		if(qq==1){
			int u,v;
			cin>>u>>v;
			val[u]=v;
		}
		else{
			int u;
			cin>>u;
			val[u]=-1;
		}
		res=1;
		solve();
		cout<<res<<"\n";
	}
}

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