oj.uz

Submission #1036758

# Submission time Handle Problem Language Result Execution time Memory
1036758 2024-07-27T16:24:55 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 476 ms 282988 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];
		return ;
	}
	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 fndd{
	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);
		return ;
	}
}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:122:11: warning: unused variable 'y' [-Wunused-variable]
  122 |   ll ty,x,y,z=1;
      |           ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 138828 KB Output is correct
2 Correct 172 ms 136784 KB Output is correct
3 Correct 150 ms 135544 KB Output is correct
4 Correct 167 ms 138192 KB Output is correct
5 Correct 158 ms 133972 KB Output is correct
6 Correct 82 ms 115644 KB Output is correct
7 Correct 90 ms 115708 KB Output is correct
8 Correct 64 ms 113260 KB Output is correct
9 Correct 168 ms 132688 KB Output is correct
10 Correct 176 ms 133160 KB Output is correct
11 Correct 200 ms 133116 KB Output is correct
12 Correct 144 ms 128848 KB Output is correct
13 Correct 166 ms 136824 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 110672 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 282 ms 282988 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 476 ms 144980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 138828 KB Output is correct
2 Correct 172 ms 136784 KB Output is correct
3 Correct 150 ms 135544 KB Output is correct
4 Correct 167 ms 138192 KB Output is correct
5 Correct 158 ms 133972 KB Output is correct
6 Correct 82 ms 115644 KB Output is correct
7 Correct 90 ms 115708 KB Output is correct
8 Correct 64 ms 113260 KB Output is correct
9 Correct 168 ms 132688 KB Output is correct
10 Correct 176 ms 133160 KB Output is correct
11 Correct 200 ms 133116 KB Output is correct
12 Correct 144 ms 128848 KB Output is correct
13 Correct 166 ms 136824 KB Output is correct
14 Incorrect 46 ms 110672 KB Output isn't correct
15 Halted 0 ms 0 KB -