oj.uz

Submission #1036748

# Submission time Handle Problem Language Result Execution time Memory
1036748 2024-07-27T16:19:10 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 454 ms 282964 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr first
#define sc second
const int mxn=5e5+5,M=1e9+7,kkk=(1<<21);
ll n,q,r,st[mxn],fn[mxn],cnt=0,sz[mxn],g[mxn],bbb;
ll ans,fuck[mxn*2],rfuck[mxn*2];
vector<ll>v[mxn];
ll ferma(ll x){
	ll num=M-2,res=1;
	while(num){
		if(num&1)res=(res*x)%M;
		x=(x*x)%M;
		num>>=1;
	}
	return res;
}
void dfs(ll z){
	sz[z]=1;
	st[z]=++cnt;
	for(auto i:v[z]){
		if(!st[i]){
			dfs(i);
			sz[z]+=sz[i];
		}
	}
	fn[z]=cnt;
}
void make(){
	fuck[0]=rfuck[0]=1;
	for(ll i=1;i<=n+r;i++){
		fuck[i]=(fuck[i-1]*i)%M;
		rfuck[i]=ferma(fuck[i]);
	}
}
ll comb(ll x,ll y,bool w){
	if(x>y){
		bbb+=(w)?-1:1;
		return 1;
	}
	ll res=fuck[y]*rfuck[x];
	res%=M;
	res*=rfuck[y-x];
	return res%M;
}
struct segment{
	ll val[kkk];
	void up(ll id,ll L,ll R,ll l,ll x){
		if(L+1==R){
			val[id]=x;
			return;
		}
		ll mid=(L+R)/2;
		if(l<mid)
			up(id*2,L,mid,l,x);
		else
			up(id*2+1,mid,R,l,x);
		val[id]=val[id*2]+val[id*2+1];
	}
	ll get(ll id ,ll L,ll R,ll l,ll r){
		if(L==l && R==r)
			return val[id];
		ll mid=(L+R)/2;
		ll res=0;
		if(l<mid)
			res+=get(id*2,L,mid,l,min(r,mid));
		if(r>mid)
			res+=get(id*2+1,mid,R,max(l,mid),r);
		return res;
	}
}seg[2];
struct fnd{
	set<ll>s[kkk];
	ll get(ll id,ll L,ll R,ll l,ll r){
		if(L==l && R==r)
			return ((s[id].size())?*s[id].rbegin():0);
		ll mid=(L+R)/2,res=((s[id].size())?*s[id].rbegin():0),x=0;
		if(l<mid){
			x=get(id*2,L,mid,l,min(r,mid));
		}
		return (x)?x:res;
	}
	void add(ll id ,ll L,ll R,ll l,ll r,ll x,bool y){
		if(L==l && R==r){
			if(y)
				s[id].insert(x);
			else
				s[id].erase(x);
			return;
		}
		ll mid=(L+R)/2;
		if(l<mid)
			add(id*2,L,mid,l,min(r,mid),x,y);
		if(r>mid)
			add(id*2+1,mid,R,max(l,mid),r,x,y);
	}
}fnd;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>r;
	for(ll i=1;i<n;i++){
		ll x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1);
	make();
	ans=comb(n-1,n+r-1,0);
	seg[0].up(1,1,n+1,1,n);
	seg[1].up(1,1,n+1,1,r);
	fnd.add(1,1,n+1,1,n+1,1,1);
	g[1]=r;
	cout<<ans<<'\n';
	cin>>q;
	while(q--){
		ll ty,x,y,z=1;
		cin>>ty;
		if(ty==1){
			cin>>x>>g[x];
			//z=fnd.get(1,1,n+1,st[x],fn[x]+1);
			fnd.add(1,1,n+1,st[x],fn[x]+1,st[x],1);
		}
		else{
			cin>>x;
			fnd.add(1,1,n+1,st[x],fn[x]+1,st[x],0);
			// z=fnd.get(1,1,n+1,st[x],fn[x]+1);
		}

		ll t1=seg[0].get(1,1,n+1,st[x],fn[x]+1)-seg[0].get(1,1,n+1,st[x],st[x]+1);
		ll t2=seg[0].get(1,1,n+1,st[z],fn[z]+1)-seg[0].get(1,1,n+1,st[z],st[z]+1);
		ll v1=seg[1].get(1,1,n+1,st[x],fn[x]+1);
		ll v2=seg[1].get(1,1,n+1,st[z],fn[z]+1);
		if(ty==1){
			ll sz1=sz[x]-t1;
			ll sz2=sz[z]-t2-sz1;
			seg[0].up(1,1,n+1,st[x],sz1);
			seg[0].up(1,1,n+1,st[z],sz2);

			ans*=ferma(comb(sz[z]-t2-1,sz[z]-t2+v2-1,1));
			ans%=M;
			//cout<<comb(sz[z]-t2-1,sz[z]-t2+v2-1,1)<<" ";
			ll val1=comb(sz1-1,sz1-1+g[x]-v1,0);
			ll val2=comb(sz2-1,sz2-1+v2-g[x]+v1,0);
			ans*=val1;
			ans%=M;
			ans*=val2;
			ans%=M;
			seg[1].up(1,1,n+1,st[x],g[x]-v1-v1);
			seg[1].up(1,1,n+1,st[z],0);
			ll w=seg[1].get(1,1,n+1,st[z],fn[z]+1);
			seg[1].up(1,1,n+1,st[z],g[z]-w-w);
		}
		else{
			ll sz1=sz[x]-t1;
			ll sz2=sz[z]-t2+sz1;
			seg[0].up(1,1,n+1,st[x],0);
			seg[0].up(1,1,n+1,st[z],sz2);
			//cout<<v1<<" "<<v2<<'\n';
			ans*=ferma(comb(sz1-1,sz1+v1-1,1));
			ans%=M;
			ans*=ferma(comb(sz[z]-t2-1,sz[z]-t2+v2-1,1));
			ans%=M;

			ll val1=comb(sz2-1,sz2-1+v2+v1,0);
			ans*=val1;
			ans%=M;

			seg[1].up(1,1,n+1,st[x],0);
			seg[1].up(1,1,n+1,st[z],0);
			ll w=seg[1].get(1,1,n+1,st[z],fn[z]+1);
			seg[1].up(1,1,n+1,st[z],g[z]-w-w);

		}
		if(bbb){
			cout<<0<<'\n';
		}
		else
			cout<<ans<<'\n';
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:120:11: warning: unused variable 'y' [-Wunused-variable]
  120 |   ll ty,x,y,z=1;
      |           ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 138836 KB Output is correct
2 Correct 149 ms 136784 KB Output is correct
3 Correct 172 ms 135504 KB Output is correct
4 Correct 161 ms 138180 KB Output is correct
5 Correct 152 ms 134228 KB Output is correct
6 Correct 79 ms 115792 KB Output is correct
7 Correct 79 ms 115536 KB Output is correct
8 Correct 70 ms 113440 KB Output is correct
9 Correct 160 ms 132688 KB Output is correct
10 Correct 173 ms 132944 KB Output is correct
11 Correct 172 ms 133088 KB Output is correct
12 Correct 151 ms 128852 KB Output is correct
13 Correct 159 ms 136860 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 110676 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 278 ms 282964 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 138836 KB Output is correct
2 Correct 149 ms 136784 KB Output is correct
3 Correct 172 ms 135504 KB Output is correct
4 Correct 161 ms 138180 KB Output is correct
5 Correct 152 ms 134228 KB Output is correct
6 Correct 79 ms 115792 KB Output is correct
7 Correct 79 ms 115536 KB Output is correct
8 Correct 70 ms 113440 KB Output is correct
9 Correct 160 ms 132688 KB Output is correct
10 Correct 173 ms 132944 KB Output is correct
11 Correct 172 ms 133088 KB Output is correct
12 Correct 151 ms 128852 KB Output is correct
13 Correct 159 ms 136860 KB Output is correct
14 Incorrect 44 ms 110676 KB Output isn't correct
15 Halted 0 ms 0 KB -