oj.uz

답안 #782238

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
782238 2023-07-13T16:36:26 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
10 / 100
 673 ms 539212 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 sega[(1<<20)];
	segres(){
		for(long long i=kaf;i<(1<<20);i++){
			sega[i]=-1;
		}
		for(long long i=1;i<kaf;i++){
			sega[i]=-1;
		}
	}
	void upd(long long i,long long w){
		if(i==0)
		{
			return ;
		}
		//return ;
		if(i<0||i>=(1<<20)){
			return ;
		}
		if((i<<1)>=(1<<20)){
			sega[i]=w;
			//return ;
			return upd((i>>1),w);
		}
	//	return ;
		////cout<<i<<" "<<w<<" "<<seg[(i<<1)]<<" "<<seg[(i<<1)^1]<<"\n";
		if((sega[(i<<1)])==-1&&sega[(i<<1)^1]==-1){
			sega[i]=-1;
			return upd((i>>1),w);
		}
		//return ;
		if((sega[(i<<1)])==-1){
			sega[i]=sega[(i<<1)^1];
			return upd((i>>1),w);
		}
		if(sega[(i<<1)^1]==-1){
			sega[i]=sega[(i<<1)];
			return upd((i>>1),w);
		}
		sega[i]=1ll*sega[(i<<1)]*sega[(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);
	//return ;
	//cout<<tedp<<" asd "<<val[pp]<<" "<<jamp<<" "<<ted<<" "<<fake<<"\n";
	res.upd(kaf+stf[pp].first,-1);
	//return ;
	if(kaf+stf[pp].first>=(1<<20)){
		return ;
	}
	res.upd(kaf+stf[pp].first,fake);
	//return ;
	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.sega[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.sega[1]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 295 ms 257152 KB Output is correct
2 Correct 276 ms 257096 KB Output is correct
3 Correct 286 ms 257036 KB Output is correct
4 Correct 291 ms 257136 KB Output is correct
5 Correct 255 ms 254284 KB Output is correct
6 Correct 187 ms 230672 KB Output is correct
7 Correct 189 ms 230348 KB Output is correct
8 Correct 185 ms 230384 KB Output is correct
9 Correct 286 ms 249120 KB Output is correct
10 Correct 286 ms 249044 KB Output is correct
11 Correct 286 ms 249164 KB Output is correct
12 Correct 295 ms 248108 KB Output is correct
13 Correct 279 ms 255256 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 185 ms 230140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 526 ms 539212 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 673 ms 259144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 295 ms 257152 KB Output is correct
2 Correct 276 ms 257096 KB Output is correct
3 Correct 286 ms 257036 KB Output is correct
4 Correct 291 ms 257136 KB Output is correct
5 Correct 255 ms 254284 KB Output is correct
6 Correct 187 ms 230672 KB Output is correct
7 Correct 189 ms 230348 KB Output is correct
8 Correct 185 ms 230384 KB Output is correct
9 Correct 286 ms 249120 KB Output is correct
10 Correct 286 ms 249044 KB Output is correct
11 Correct 286 ms 249164 KB Output is correct
12 Correct 295 ms 248108 KB Output is correct
13 Correct 279 ms 255256 KB Output is correct
14 Incorrect 185 ms 230140 KB Output isn't correct
15 Halted 0 ms 0 KB -