Submission #935557

#	Time	Username	Problem	Language	Result	Execution time	Memory
935557		PM1	Sumtree (INOI20_sumtree)	C++17	10 / 100	3072 ms	49380 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=6e5+5,M=1e9+7;
int n,q,r;
ll fuck[mxn],rfuck[mxn],ans=1,par[mxn],mark[mxn],sz[mxn],mize[mxn];
vector<int>v[mxn];
ll ferma(ll x){
	ll res=1,num=M-2;
	while(num){
		if(num&1)res=(res*x)%M;
		x=(x*x)%M;
		num/=2;
	}
	return res;
}
ll comb(ll x,ll y){
	return (((fuck[y]*rfuck[x])%M)*rfuck[y-x])%M;
}
void dfs(int z){
	sz[z]=1;
	mize[z]=0;
	for(auto i:v[z]){
		if(par[z]!=i){
			par[i]=z;
			dfs(i);
			sz[z]+=sz[i];
			mize[z]+=mize[i];
		}
	}
	if(mark[z]){
		assert(mark[z]>=mize[z]);
		ans=(ans*comb(sz[z]-1,sz[z]+(mark[z]-mize[z])-1))%M;
		mize[z]=mark[z];
		sz[z]=0;//cout<<z<<" "<<comb(sz[z]-1,sz[z]+(mark[z]-mize[z])-1)<<'\n';
	}
	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>r;
	fuck[0]=1;
	rfuck[0]=1;
	for(int i=1;i<mxn;i++){
		fuck[i]=(fuck[i-1]*i)%M;
		rfuck[i]=ferma(fuck[i]);
	}
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	mark[1]=r;
	dfs(1);
	cout<<ans<<'\n';
	cin>>q;
	while(q--){
		ans=1;
		int ty,x,y;
		cin>>ty;
		if(ty==1){
			cin>>x>>y;
			mark[x]=y;
		}
		else{
			cin>>x;
			mark[x]=0;
		}
		dfs(1);
		cout<<ans%M<<'\n';
	}
	return 0;
}

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