oj.uz

Submission #624121

# Submission time Handle Problem Language Result Execution time Memory
624121 2022-08-07T09:54:18 Z Arinoor Sumtree (INOI20_sumtree) C++17
10 / 100
 331 ms 68516 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'
#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e6 + 10;
const int maxlg = 19;
const int maxf = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

int n, fact[maxf], invfact[maxf];
int val[maxn], tag[maxn];
int par[maxn][maxlg], sz[maxn], st[maxn], ed[maxn], tme = 1;
ll fenC[maxn], fenS[maxn], fenP[maxn];
vector<int> G[maxn];

int add(int a, int b){
	int c = a + b;
	if(c >= mod) c -= mod;
	if(c < 0) c += mod;
	return c;
}

int mul(int a, int b){
	return 1ll * a * b % mod;
}

int pwr(int a, int b){
	int res = 1;
	for(; b; b >>= 1, a = mul(a, a)) if(b & 1) res = mul(res, a);
	return res;
}

int inv(int a){
	return pwr(a, mod - 2);
}

int C(int a, ll b){
	if(a > b)
		return 0;
	if(b < 0 or b >= maxf or a < 0 or a >= maxf or b - a < 0 or b - a >= maxf){
		cout << "-2\n";
		exit(0);
	}
	return mul(fact[b], mul(invfact[a], invfact[b - a]));
}

void update_fact(){
	fact[0] = invfact[0] = 1;
	for(int i = 1; i < maxf; i ++){
		fact[i] = mul(fact[i - 1], i);
		invfact[i] = inv(fact[i]);
	}
	/*
	invfact[maxf - 1] = inv(fact[maxf - 1]);
	for(int i = maxf - 2; ~i; i --)
		invfact[i] = mul(invfact[i + 1], i + 1);
		*/
}

void add(ll *fen, int i, ll x){
	for(; i <= n; i += i & -i)
		fen[i] += x;
}

ll get(ll *fen, int i){
	ll res = 0;
	for(; i; i -= i & -i)
		res += fen[i];
	return res;
}

ll get(ll *fen, int l, int r){
	return get(fen, r) - get(fen, l - 1);
}

void dfs(int v, int p = 0){
	par[v][0] = p;
	for(int i = 1; i < maxlg and par[v][i - 1]; i ++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	st[v] = tme;
	sz[v] = 1;
	for(int u : G[v]){
		if(u ^ p){
			tme ++;
			dfs(u, v);
			sz[v] += sz[u];
		}
	}
	ed[v] = tme;
}

int get_val(int v){
	int cnt = sz[v] - get(fenC, st[v] + 1, ed[v]);
	ll sum = tag[v] - get(fenS, st[v] + 1, ed[v]);
	return C(cnt - 1, cnt + sum - 1);
}

int find(int v){
	int x = get(fenP, st[v]);
	for(int i = maxlg - 1; ~i; i --){
		int u = par[v][i];
		if(!u) continue;
		if(get(fenP, st[u]) == x)
			v = u;
	}
	return par[v][0];
}

int main(){
	ios;
	update_fact();
	int r;
	cin >> n >> r;
	for(int i = 0; i < n - 1; i ++){
		int u, v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1);
	memset(tag, -1, sizeof tag);
	tag[1] = r;
	add(fenP, st[1] + 1, 1); add(fenP, ed[1] + 1, -1);
	for(int i = 2; i <= n; i ++)
		val[i] = 1;
	val[1] = get_val(1);
	int ans = val[1];
	cout << ans << '\n';
	int q; cin >> q;
	int Cnt = 0;
	while(q--){
		int t, v;
		cin >> t >> v;
		if(t == 1){
			int x; cin >> x;
			tag[v] = x;
			val[v] = get_val(v);
			if(val[v])
				ans = mul(ans, val[v]);
			else
				Cnt ++;
			int cnt = sz[v] - get(fenC, st[v] + 1, ed[v]);
			add(fenC, st[v], cnt);
			ll sum = tag[v] - get(fenS, st[v] + 1, ed[v]);
			add(fenS, st[v], sum);
			add(fenP, st[v] + 1, 1); add(fenP, ed[v] + 1, -1);
			int p = find(v);
			if(inv(val[p]))
				ans = mul(ans, inv(val[p]));
			else
				Cnt --;
			val[p] = get_val(p);
			if(val[p])
				ans = mul(ans, val[p]);
			else
				Cnt ++;
		}
		else{
			if(inv(val[v]))
				ans = mul(ans, inv(val[v]));
			else
				Cnt --;
			val[v] = 1;
			int cnt = sz[v] - get(fenC, st[v] + 1, ed[v]);
			add(fenC, st[v], -cnt);
			ll sum = tag[v] - get(fenS, st[v] + 1, ed[v]);
			add(fenS, st[v], -sum);
			add(fenP, st[v] + 1, -1); add(fenP, ed[v] + 1, 1);
			int p = find(v);
			if(inv(val[p]))
				ans = mul(ans, inv(val[p]));
			else
				Cnt --;
			val[p] = get_val(p);
			if(val[p])
				ans = mul(ans, val[p]);
			else
				Cnt ++;
			tag[v] = -1;
		}
		if(Cnt)
			cout << "0\n";
		else
			cout << ans << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 67792 KB Output is correct
2 Correct 298 ms 67664 KB Output is correct
3 Correct 319 ms 67744 KB Output is correct
4 Correct 298 ms 67664 KB Output is correct
5 Correct 278 ms 63692 KB Output is correct
6 Correct 177 ms 36156 KB Output is correct
7 Correct 174 ms 35992 KB Output is correct
8 Correct 188 ms 36016 KB Output is correct
9 Correct 283 ms 60064 KB Output is correct
10 Correct 331 ms 60048 KB Output is correct
11 Correct 289 ms 60048 KB Output is correct
12 Correct 292 ms 58780 KB Output is correct
13 Correct 289 ms 65272 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 67792 KB Output is correct
2 Correct 298 ms 67664 KB Output is correct
3 Correct 319 ms 67744 KB Output is correct
4 Correct 298 ms 67664 KB Output is correct
5 Correct 278 ms 63692 KB Output is correct
6 Correct 177 ms 36156 KB Output is correct
7 Correct 174 ms 35992 KB Output is correct
8 Correct 188 ms 36016 KB Output is correct
9 Correct 283 ms 60064 KB Output is correct
10 Correct 331 ms 60048 KB Output is correct
11 Correct 289 ms 60048 KB Output is correct
12 Correct 292 ms 58780 KB Output is correct
13 Correct 289 ms 65272 KB Output is correct
14 Incorrect 178 ms 35552 KB Output isn't correct
15 Halted 0 ms 0 KB -