oj.uz

Submission #781955

# Submission time Handle Problem Language Result Execution time Memory
781955 2023-07-13T14:08:05 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
10 / 100
 716 ms 520236 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);
	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);
	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 307 ms 257756 KB Output is correct
2 Correct 272 ms 257692 KB Output is correct
3 Correct 271 ms 257744 KB Output is correct
4 Correct 278 ms 257748 KB Output is correct
5 Correct 277 ms 255200 KB Output is correct
6 Correct 179 ms 230592 KB Output is correct
7 Correct 182 ms 230388 KB Output is correct
8 Correct 179 ms 230440 KB Output is correct
9 Correct 288 ms 250028 KB Output is correct
10 Correct 274 ms 249520 KB Output is correct
11 Correct 281 ms 249756 KB Output is correct
12 Correct 275 ms 249220 KB Output is correct
13 Correct 258 ms 256112 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 175 ms 230116 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 509 ms 520236 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 716 ms 259996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 257756 KB Output is correct
2 Correct 272 ms 257692 KB Output is correct
3 Correct 271 ms 257744 KB Output is correct
4 Correct 278 ms 257748 KB Output is correct
5 Correct 277 ms 255200 KB Output is correct
6 Correct 179 ms 230592 KB Output is correct
7 Correct 182 ms 230388 KB Output is correct
8 Correct 179 ms 230440 KB Output is correct
9 Correct 288 ms 250028 KB Output is correct
10 Correct 274 ms 249520 KB Output is correct
11 Correct 281 ms 249756 KB Output is correct
12 Correct 275 ms 249220 KB Output is correct
13 Correct 258 ms 256112 KB Output is correct
14 Incorrect 175 ms 230116 KB Output isn't correct
15 Halted 0 ms 0 KB -