Submission #635415

#	Time	Username	Problem	Language	Result	Execution time	Memory
635415		S2speed	Sumtree (INOI20_sumtree)	C++17	100 / 100	576 ms	64972 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define sze(x) (int)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;

const ll maxn = 2e5 + 17 , maxc = 6e5 + 17 , md = 1e9 + 7 , inf = 2e8;

struct fentree {

	int sz;
	vector<int> val;

	void init(int n){
		sz = n;
		val.assign(sz , 0);
		return;
	}

	void add(int i , int k){
		if(i == -1) return;
		int h = i;
		while(h < sz){
			val[h] += k;
			h |= (h + 1);
		}
		return;
	}

	int cal(int i){
		int h = i , res = 0;
		while(h > -1){
			res += val[h];
			h &= (h + 1); h--;
		}
		return res;
	}

	int cal(int l , int r){
		return cal(r - 1) - cal(l - 1);
	}

};

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

ll fact[maxc] , _fact[maxc];

void fact_build(){
	fact[0] = 1;
	for(ll i = 1 ; i < maxc ; i++){
		fact[i] = fact[i - 1] * i % md;
	}
	_fact[maxc - 1] = tav(fact[maxc - 1] , md - 2);
	for(ll i = maxc - 2 ; ~i ; i--){
		_fact[i] = _fact[i + 1] * (i + 1) % md;
	}
	return;
}

ll chs(ll n , ll k){
	if(n < k) return 0;
	return fact[n] * _fact[k] % md * _fact[n - k] % md;
}

ll _chs(ll n , ll k){
	if(n < k) return 0;
	return _fact[n] * fact[k] % md * fact[n - k] % md;
}

fentree zt , at , ft;
ll res = 1;
int cnt;
int a[maxn] , z[maxn];
vector<int> adj[maxn];
int jad[maxn][20] , bt[maxn] , et[maxn] , tme = 0;

void pDFS(int r , int par){
	bt[r] = tme++;
	z[r] = 1;
	jad[r][0] = par;
	for(int j = 1 ; j < 20 ; j++){
		if(jad[r][j - 1] == -1) break;
		jad[r][j] = jad[jad[r][j - 1]][j - 1];
	}
	for(auto i : adj[r]){
		if(i == par) continue;
		pDFS(i , r);
		z[r] += z[i];
	}
	et[r] = tme;
	return;
}

void rem(ll n , ll k){
	ll h = _chs(n , k);
	if(h == 0){
		cnt--;
	} else {
		res *= h; res %= md;
	}
	return;
}

void add(ll n , ll k){
	ll h = chs(n , k);
	if(h == 0){
		cnt++;
	} else {
		res *= h; res %= md;
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(jad , -1 , sizeof(jad));
	fact_build();
	ll n;
	cin>>n>>a[0];
	for(ll i = 1 ; i < n ; i++){
		ll v , u;
		cin>>v>>u; v--; u--;
		adj[v].push_back(u); adj[u].push_back(v);
	}
	pDFS(0 , -1);
	int q;
	cin>>q;
	res = chs(n + a[0] - 1 , n - 1);
	cout<<res<<'\n';
	ft.init(n); zt.init(n); at.init(n);
	for(int e = 0 ; e < q ; e++){
		int t;
		cin>>t;
		if(t == 2){
			int i;
			cin>>i; i--;
			int v = i , pr = ft.cal(bt[i]) - 1;
			for(int j = 19 ; ~j ; j--){
				if(jad[v][j] == -1) continue;
				int u = jad[v][j] , h = ft.cal(bt[u]);
				if(h == pr){
					v = u;
				}
			}
			int zv = z[v] - zt.cal(bt[v] , et[v]) , av = a[v] - at.cal(bt[v] , et[v]);
			rem(zv + av - 1 , zv - 1);
			int zi = z[i] - zt.cal(bt[i] , et[i]) , ai = a[i] - at.cal(bt[i] , et[i]);
			rem(zi + ai - 1 , zi - 1);
			int ji = jad[i][0] , jv = jad[v][0];
			zt.add(bt[ji] , -zi);
			at.add(bt[ji] , -ai);
			if(jv != -1){
				zt.add(bt[jv] , zi);
				at.add(bt[jv] , ai);
			}
			zv = z[v] - zt.cal(bt[v] , et[v]); av = a[v] - at.cal(bt[v] , et[v]);
			add(zv + av - 1 , zv - 1);
			ft.add(bt[i] , -1); ft.add(et[i] , 1);
		} else {
			int i , x;
			cin>>i>>x; i--; a[i] = x;
			int v = i , pr = ft.cal(bt[i]);
			for(int j = 19 ; ~j ; j--){
				if(jad[v][j] == -1) continue;
				int u = jad[v][j] , h = ft.cal(bt[u]);
				if(h == pr){
					v = u;
				}
			}
//			cout<<v<<'\n';
			int zv = z[v] - zt.cal(bt[v] , et[v]) , av = a[v] - at.cal(bt[v] , et[v]);
//			cout<<zv<<' '<<av<<'\n';
//			cout<<res<<' ';
			rem(zv + av - 1 , zv - 1);
//			cout<<res<<' ';
			int zi = z[i] - zt.cal(bt[i] , et[i]) , ai = a[i] - at.cal(bt[i] , et[i]);
			add(zi + ai - 1 , zi - 1);
//			cout<<res<<' ';
			int ji = jad[i][0] , jv = jad[v][0];
			zt.add(bt[ji] , zi);
			at.add(bt[ji] , ai);
			if(jv != -1){
				zt.add(bt[jv] , -zi);
				at.add(bt[jv] , -ai);
			}
			zv = z[v] - zt.cal(bt[v] , et[v]); av = a[v] - at.cal(bt[v] , et[v]);
			add(zv + av - 1 , zv - 1);
//			cout<<res<<'\n';
			ft.add(bt[i] , 1); ft.add(et[i] , -1);
		}
		cout<<(cnt > 0 ? 0 : res)<<'\n';
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30