oj.uz

Submission #781925

# Submission time Handle Problem Language Result Execution time Memory
781925 2023-07-13T13:36:53 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
10 / 100
 466 ms 206904 KB 
#include<bits/stdc++.h>
using namespace std;
int n,k;
const int maxn=200000+10,maxm=500000+10;
vector<int>adj[maxn],child[maxn];
int par[maxn],val[maxn],link[maxn],wa[maxn],cnt[maxn],asd,timea=0,high[maxn],fact[maxm],revfact[maxm],mod=1e9+7;
pair<int,int>stf[maxn];

int kaf=(1<<19);

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

	void upd(int i,int l,int r,int tl,int tr,int 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 ;
		}
		int 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(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		int m=(l+r)>>1;
		int ret=pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
		return ret;
	}
	void upd(int 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(int i=kaf;i<(1<<20);i++){
			seg[i]=-1;
		}
		for(int i=1;i<kaf;i++){
			seg[i]=-1;
		}
	}
	void upd(int 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(int i=1;i<maxm;i++){
		fact[i]=1ll*fact[i-1]*i%mod;
	}
	revfact[maxm-1]=mypow(fact[maxm-1],mod-2);
	for(int i=maxm-2;i>=0;i--){
		revfact[i]=1ll*revfact[i+1]*(i+1)%mod;
	}
}

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

void dfs(int u,int 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;
}

int hes(int a,int b){
	a++;
	//cout<<"wtf: "<<a<<" "<<b<<"\n";
	int 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(int u,int w){
	wa[u]=w;
	val[u]=w;
	int pp=segbal.get(stf[u].first+kaf).second;
	long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	int 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);
	int tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	int 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(int u){
	int pp=segbal.get(stf[u].first+kaf).second;
	long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	int 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);
	int tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	int 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(int i=0;i<n-1;i++){
		int 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;
	int q;
	cin>>q;
	asd=1;
	cout<<res.seg[1]<<"\n";
	for(;asd<=q;asd++){
		int qq;
		cin>>qq;
		if(qq==1){
			int u,w;
			cin>>u>>w;
			upd(u,w);
		}
		else{
			int u;
			cin>>u;
			del(u);
		}
		cout<<res.seg[1]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 97104 KB Output is correct
2 Correct 143 ms 97152 KB Output is correct
3 Correct 142 ms 97132 KB Output is correct
4 Correct 143 ms 97080 KB Output is correct
5 Correct 112 ms 94676 KB Output is correct
6 Correct 38 ms 71708 KB Output is correct
7 Correct 39 ms 71340 KB Output is correct
8 Correct 46 ms 71372 KB Output is correct
9 Correct 179 ms 87172 KB Output is correct
10 Correct 136 ms 87124 KB Output is correct
11 Correct 167 ms 87140 KB Output is correct
12 Correct 125 ms 86396 KB Output is correct
13 Correct 123 ms 95564 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 71212 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 235 ms 206904 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 466 ms 97668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 97104 KB Output is correct
2 Correct 143 ms 97152 KB Output is correct
3 Correct 142 ms 97132 KB Output is correct
4 Correct 143 ms 97080 KB Output is correct
5 Correct 112 ms 94676 KB Output is correct
6 Correct 38 ms 71708 KB Output is correct
7 Correct 39 ms 71340 KB Output is correct
8 Correct 46 ms 71372 KB Output is correct
9 Correct 179 ms 87172 KB Output is correct
10 Correct 136 ms 87124 KB Output is correct
11 Correct 167 ms 87140 KB Output is correct
12 Correct 125 ms 86396 KB Output is correct
13 Correct 123 ms 95564 KB Output is correct
14 Incorrect 41 ms 71212 KB Output isn't correct
15 Halted 0 ms 0 KB -