oj.uz

Submission #782199

# Submission time Handle Problem Language Result Execution time Memory
782199 2023-07-13T16:16:40 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
10 / 100
 544 ms 269096 KB 
#include<bits/stdc++.h>
using namespace std;
long long n,k;
const long long maxn=2000000+10,maxm=5000000+10;
vector<long long>adj[maxn],child[maxn];
long long par[maxn],val[maxn],link[maxn],wa[maxn],cnt[maxn],asd,timea=0,high[maxn],fact[maxm],revfact[maxm],mod=1e9+7;
pair<long long,long long>stf[maxn];

long long kaf=(1<<19);

struct segment{
	set<pair<long long,long long>>seg[(1<<20)];
	pair<long long,long long> get(long long i){
		if(i==0){
			return make_pair(0,0);
		}
		if((long long)seg[i].size()==0){
			return get((i>>1));
		}
		auto x=*seg[i].rbegin();
		return max(get((i>>1)),x);
	}
	void del(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].erase(make_pair(high[w],w));
			return ;
		}
		long long m=(l+r)>>1;
		del((i<<1),l,m,tl,tr,w);
		del((i<<1)^1,m+1,r,tl,tr,w);
	}

	void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].insert(make_pair(high[w],w));
			return ;
		}
		long long m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
	}
}segbal;

struct segjam{
	long long seg[(1<<20)];
	long long pors(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		long long m=(l+r)>>1;
		long long ret=pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
		return ret;
	}
	void upd(long long i,long long w){
		if(i==0){
			return ;
		}
		seg[i]+=w;
		upd((i>>1),w);
	}
}segjam,segted;

struct segres{
	long long seg[(1<<20)];
	segres(){
		for(long long i=kaf;i<(1<<20);i++){
			seg[i]=-1;
		}
		for(long long i=1;i<kaf;i++){
			seg[i]=-1;
		}
	}
	void upd(long long i,long long w){
		if(i==0)
		{
			return ;
		}
		if(i>=kaf){
			seg[i]=w;
			return upd((i>>1),w);
		}
		////cout<<i<<" "<<w<<" "<<seg[(i<<1)]<<" "<<seg[(i<<1)^1]<<"\n";
		if((seg[(i<<1)])==-1&&seg[(i<<1)^1]==-1){
			seg[i]=-1;
			return upd((i>>1),w);
		}
		if((seg[(i<<1)])==-1){
			seg[i]=seg[(i<<1)^1];
			return upd((i>>1),w);
		}
		if(seg[(i<<1)^1]==-1){
			seg[i]=seg[(i<<1)];
			return upd((i>>1),w);
		}
		seg[i]=1ll*seg[(i<<1)]*seg[(i<<1)^1]%mod;
		return upd((i>>1),w);
	}

}res;

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

long long c(long long i,long long j){
	//cout<<"av: "<<i<<" "<<j<<"\n";
	if(i<0||j<0||i<j){
		return 0;
	}
	//cout<<"dov: "<<i<<" "<<j<<"\n";
	long long ret=1ll*fact[i]*revfact[j]%mod*revfact[i-j]%mod;
	return ret;
}

void dfs(long long u,long long para=0){
	cnt[u]=1;
	high[u]=high[para]+1;
	timea++;
	stf[u].first=timea;
	par[u]=para;
	for(auto x:adj[u]){
		if(x!=para){
			child[u].push_back(x);
			dfs(x,u);
			cnt[u]+=cnt[x];
		}
	}
	stf[u].second=timea;
}

long long hes(long long a,long long b){
	a++;
	//cout<<"wtf: "<<a<<" "<<b<<"\n";
	long long ret=c(b+a-1,a-1);	
	return ret;
}

void tof(){
	//cout<<"salam"<<endl;
	res.upd(stf[1].first+kaf,hes(n-1,val[1]));
	//cout<<"vas "<<n-1<<" "<<val[1]<<" "<<hes(n-1,val[1])<<endl;
	segbal.upd(1,0,kaf-1,stf[1].first+1,stf[1].second,1);
	//cout<<"akh"<<endl;
	link[1]=0;
}

void upd(long long u,long long w){
	wa[u]=w;
	val[u]=w;
	long long pp=segbal.get(stf[u].first+kaf).second;
	long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	long long ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	//return ;
	segted.upd(kaf+stf[u].first,ted);
	segbal.upd(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
	segjam.upd(kaf+stf[u].first,-jam+w);
	return ;
	long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	long long fake=hes(tedp-1,val[pp]-jamp);
	//cout<<tedp<<" asd "<<val[pp]<<" "<<jamp<<" "<<ted<<" "<<fake<<"\n";
	res.upd(kaf+stf[pp].first,-1);
	res.upd(kaf+stf[pp].first,fake);
	fake=hes(ted-1,val[u]-jam);
	//cout<<ted<<" sec "<<val[u]<<" "<<jam<<"\n";
	res.upd(stf[u].first+kaf,fake);
}

void del(long long u){
	long long pp=segbal.get(stf[u].first+kaf).second;
	long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	long long ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	segted.upd(kaf+stf[u].first,-ted);
	segbal.del(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
	segjam.upd(kaf+stf[u].first,+jam-wa[u]);
	long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	long long fake=hes(tedp-1,val[pp]-jamp);
	res.upd(kaf+stf[pp].first,-1);
	res.upd(kaf+stf[pp].first,fake);
	res.upd(stf[u].first+kaf,-1);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	aval();
	cin>>n>>k;
	for(long long i=0;i<n-1;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1);
	segjam.upd(stf[1].first+kaf,k);
	////cout<<"salam"<<endl;
	val[1]=k;
	tof();
	//cout<<"salam"<<endl;
	long long q;
	cin>>q;
	asd=1;
	cout<<res.seg[1]<<"\n";
	for(;asd<=q;asd++){
		long long qq;
		cin>>qq;
		if(qq==1){
			long long u,w;
			cin>>u>>w;
			upd(u,w);
		}
		else{
			long long u;
			cin>>u;
			del(u);
		}
		cout<<res.seg[1]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 257132 KB Output is correct
2 Correct 284 ms 257048 KB Output is correct
3 Correct 280 ms 257100 KB Output is correct
4 Correct 284 ms 257064 KB Output is correct
5 Correct 285 ms 254448 KB Output is correct
6 Correct 185 ms 230532 KB Output is correct
7 Correct 186 ms 230292 KB Output is correct
8 Correct 185 ms 230364 KB Output is correct
9 Correct 313 ms 249092 KB Output is correct
10 Correct 287 ms 249032 KB Output is correct
11 Correct 293 ms 249268 KB Output is correct
12 Correct 283 ms 248120 KB Output is correct
13 Correct 271 ms 255296 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 257132 KB Output is correct
2 Correct 284 ms 257048 KB Output is correct
3 Correct 280 ms 257100 KB Output is correct
4 Correct 284 ms 257064 KB Output is correct
5 Correct 285 ms 254448 KB Output is correct
6 Correct 185 ms 230532 KB Output is correct
7 Correct 186 ms 230292 KB Output is correct
8 Correct 185 ms 230364 KB Output is correct
9 Correct 313 ms 249092 KB Output is correct
10 Correct 287 ms 249032 KB Output is correct
11 Correct 293 ms 249268 KB Output is correct
12 Correct 283 ms 248120 KB Output is correct
13 Correct 271 ms 255296 KB Output is correct
14 Incorrect 185 ms 230140 KB Output isn't correct
15 Halted 0 ms 0 KB -