| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 635501 |
2022-08-26T10:47:11 Z |
K4YAN |
Sumtree (INOI20_sumtree) |
C++17 |
|
262 ms |
187208 KB |
//Be Name Khoda
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define all(x) x.begin(), x.end()
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
const ll mxn = 2e5 + 16, MX = 3e5 + 16, md = 1e9 + 7;
ll n, r, t, q, w, cnt, pw;
ll st[mxn], ft[mxn], dp[mxn], h[mxn], subt[mxn], R[mxn], fact[MX], taq[MX], par[mxn][19];
vector<ll> adj[mxn];
bitset<mxn> mark;
set<int> s[2 * MX];
inline ll tav(ll a, ll b) {
ll res = 1;
while(b > 0) {
if(b & 1) res = res * a % md;
a = a * a % md, b >>= 1;
} return res;
}
inline ll chs(ll a, ll b) {
if(a < 0 || b > a) return 0;
return fact[a] * taq[b] % md * taq[a - b] % md;
}
inline void fun() {
fact[0] = 1;
for(int i = 1; i < MX; i++) {
fact[i] = fact[i - 1] * i % md;
} taq[MX - 1] = tav(fact[MX - 1], md - 2);
for(int i = MX - 2; i > -1; i--) {
taq[i] = taq[i + 1] * (i + 1) % md;
} return;
}
void DFS(int v) {
mark.set(v);
st[v] = q++, subt[v] = 1;
for(int i = 1; i < 19; i++) {
par[v][i] = par[par[v][i - 1]][i - 1];
} for(auto u : adj[v]) {
if(!mark[u]) {
par[u][0] = v;
h[u] = h[v] + 1;
DFS(u);
subt[v] += subt[u];
}
} ft[v] = q;
return;
}
inline int find_par(int v, int x) {
for(int i = 18; i > -1; i--) {
if(x & (1 << i)) {
v = par[v][i];
x -= (1 << i);
if(x == 0) return v;
}
} return v;
}
struct segtree {
int sz = 1;
vector<pll> v;
void init(ll n) {
while(sz < n) sz <<= 1;
v.assign(2 * sz, {0, 0});
return;
}
void set(int i, pll p, int x, int lx, int rx) {
if(rx - lx == 1) {
v[x] = p;
return;
} int m = (lx + rx) >> 1;
if(i < m) {
set(i, p, 2 * x + 1, lx, m);
} else {
set(i, p, 2 * x + 2, m, rx);
} v[x].first = v[2 * x + 1].first + v[2 * x + 2].first;
v[x].second = v[2 * x + 1].second + v[2 * x + 2].second;
return;
}
void set(int i, pll p) {
set(i, p, 0, 0, sz);
return;
}
pll ask(int l, int r, int x, int lx, int rx) {
if(rx <= l || r <= lx) return {0, 0};
if(l <= lx && rx <= r) {
return v[x];
} int m = (lx + rx) >> 1;
pll a = ask(l, r, 2 * x + 1, lx, m);
pll b = ask(l, r, 2 * x + 2, m, rx);
return {a.first + b.first, a.second + b.second};
}
pll ask(int l, int r) {
return ask(l, r, 0, 0, sz);
}
}; segtree stt;
struct fp {
int sz = 1;
void init(ll n) {
while(sz < n) sz <<= 1;
return;
}
void add(int l, int r, int q, int x, int lx, int rx) {
if(rx <= l || r <= lx) return;
if(l <= lx && rx <= r) {
s[x].insert(-q);
return;
} int m = (lx + rx) >> 1;
add(l, r, q, 2 * x + 1, lx, m);
add(l, r, q, 2 * x + 2, m, rx);
return;
}
void add(int l, int r, int q) {
add(l, r, q, 0, 0, sz);
return;
}
int ask(int i, int x, int lx, int rx) {
int a = 0;
if(int(s[x].size()) > 0) {
a = *(s[x].begin()), a = -a;
}
if(rx - lx == 1) {
if(int(s[x].size()) == 0) return 0;
return -1 * (*(s[x].begin()));
} int m = (lx + rx) >> 1;
if(i < m) {
return max(a, ask(i, 2 * x + 1, lx, m));
} else {
return max(a, ask(i, 2 * x + 2, m, rx));
}
}
int ask(int i) {
return ask(i, 0, 0, sz);
}
void rem(int l, int r, int q, int x, int lx, int rx) {
if(rx <= l || r <= lx) return;
if(l <= lx && rx <= r) {
s[x].erase(-q);
return;
} int m = (lx + rx) >> 1;
rem(l, r, q, 2 * x + 1, lx, m);
rem(l, r, q, 2 * x + 2, m, rx);
return;
}
void rem(int l, int r, int q) {
rem(l, r, q, 0, 0, sz);
return;
}
}; fp fpar;
inline void input() {
cin >> n >> r;
for(int i = 1; i < n; i++) {
cin >> q >> w;
adj[q].push_back(w);
adj[w].push_back(q);
} cin >> t;
}
inline void solve() {
fun(); q = 0;
DFS(1);
fill(dp, dp + mxn, 1);
dp[1] = pw = chs(r + n - 1, n - 1);
cout << pw << "\n";
stt.init(n), fpar.init(n);
fpar.add(1, n, 0); R[1] = r;
for(int tt = 0; tt < t; tt++) {
cin >> q;
if(q == 1) {
cin >> q >> w;
R[q] = w;
ll v = fpar.ask(st[q]), x, rp, sp;
pll p;
v = find_par(q, h[q] - v);
if(dp[v] == 0) cnt--;
else pw = pw * tav(dp[v], md - 2) % md;
p = stt.ask(st[q] + 1, ft[q]);
rp = R[q] - p.first, sp = subt[q] - p.second;
x = chs(rp + sp - 1, sp - 1);
if(x == 0) cnt++, dp[q] = 0;
else {
dp[q] = x, pw = pw * x % md;
} stt.set(st[q], {rp, sp});
fpar.add(st[q] + 1, ft[q], h[q]);
p = stt.ask(st[v] + 1, ft[v]);
rp = R[v] - p.first, sp = subt[v] - p.second;
x = chs(rp + sp - 1, sp - 1);
if(x == 0) cnt++, dp[v] = 0;
else {
dp[v] = x, pw = pw * x % md;
} stt.set(st[v], {rp, sp});
if(cnt == 0) {
cout << pw << "\n";
} else {
cout << "0\n";
}
continue;
} cin >> q;
ll v = fpar.ask(st[q]), x, rp, sp;
pll p;
v = find_par(q, h[q] - v);
if(dp[q] == 0) {
cnt--, dp[q] = 1;
} else {
pw = pw * tav(dp[q], md - 2) % md, dp[q] = 1;
} R[q] = 0;
stt.set(st[q], {0, 0});
fpar.rem(st[q] + 1, ft[q], h[q]);
if(dp[v] == 0) {
cnt--;
} else {
pw = pw * tav(dp[v], md - 2) % md;
}
p = stt.ask(st[v] + 1, ft[v]);
rp = R[v] - p.first, sp = subt[v] - p.second;
x = chs(rp + sp - 1, sp - 1);
if(x == 0) {
cnt++, dp[x] = 0;
} else {
dp[x] = x, pw = pw * x % md;
} stt.set(st[v], {rp, sp});
if(cnt == 0) {
cout << pw << "\n";
} else {
cout << "0\n";
}
}
return;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
input(), solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
189 ms |
98852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
39448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
243 ms |
102104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
262 ms |
187208 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
189 ms |
98852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
