#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast,unroll-loops")
//#pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define ff first
#define ss second
void dbg(){
cerr << endl;
}
template<typename Head, typename... Tail> void dbg(Head h, Tail... t){
cerr << " " << h << ",";
dbg(t...);
}
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbg(__VA_ARGS__)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
// #ifndef ONLINE_JUDGE
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// #endif
}
const ll mod = 1e9 + 7, maxn = 5e5 + 5, lg = 21, inf = ll(1e9) + 5;
struct SegMul{
vector<ll> seg;
int n;
SegMul(int n): n(n){
seg.assign(n<<1, 1);
}
void upd(int i, ll k){
for(i += n, seg[i] = k; i > 1; i >>= 1) seg[i>>1] = seg[i]*seg[i^1]%mod;
}
ll get(){
return seg[1];
}
};
struct Fen{
vector<ll> fen;
Fen(int n){
fen.assign(n + 5, 0);
}
void upd(int i, ll k){
for(i++; i < sz(fen); i += i&-i) fen[i] += k;
}
ll get(int i){
ll res = 0;
for(i++; i; i -= i&-i) res += fen[i];
return res;
}
ll get(int l, int r){
return get(r - 1) - get(l - 1);
}
};
ll pw(ll a, ll b){
if(!b) return 1;
ll k = pw(a, b>>1ll);
return k*k%mod*(b&1ll?a:1ll)%mod;
}
ll fac[maxn], inv[maxn];
ll C(int n, int r){
if(r < 0 || r > n) return 0;
return fac[n]*inv[r]%mod*inv[n-r]%mod;
}
vector<int> adj[maxn];
int st[maxn], en[maxn], par[maxn][lg], t, cnt[maxn];
ll val[maxn];
void dfs(int r, int p){
cnt[r] = 1;
st[r] = t++;
par[r][0] = p;
rep(i,1,lg) par[r][i] = par[par[r][i-1]][i-1];
for(int c: adj[r]) if(c - p){
dfs(c, r);
cnt[r] += cnt[c];
}
en[r] = t;
}
int main(){ IOS();
fac[0] = inv[0] = 1;
rep(i,1,maxn){
fac[i] = fac[i-1]*i%mod;
inv[i] = pw(fac[i], mod-2);
}
int n, r; cin >> n >> r;
val[0] = r;
rep(i,1,n){
int u, v; cin >> u >> v; u--, v--;
adj[u].pb(v), adj[v].pb(u);
}
dfs(0, 0);
SegMul smul(n); smul.upd(0, C(r + n - 1, r));
Fen fen_par(n); fen_par.upd(st[0], 1), fen_par.upd(en[0], -1);
Fen cnt_sub(n); cnt_sub.upd(0, n);
Fen sum_val(n); sum_val.upd(0, r);
auto get_par = [&](int r){
int vl = fen_par.get(st[r]);
per(i,lg-1,0){
int p = par[r][i];
if(vl == fen_par.get(st[p])) r = p;
}
return par[r][0];
};
auto add = [&](int r, int x){
int p = get_par(r);
fen_par.upd(st[r], 1), fen_par.upd(en[r], -1);
ll fl = cnt_sub.get(st[r], en[r]);
ll emp = cnt[r] - fl;
cnt_sub.upd(st[r], emp);
cnt_sub.upd(st[p], -emp);
sum_val.upd(st[r], val[r] = x - sum_val.get(st[r], en[r]));
smul.upd(r, C(val[r] + emp - 1, val[r]));
sum_val.upd(st[p], -val[r]); val[p] -= val[r];
emp = cnt_sub.get(st[p], st[p] + 1);
smul.upd(p, C(val[p] + emp - 1, val[p]));
};
auto rem = [&](int r){
fen_par.upd(st[r], -1), fen_par.upd(en[r], 1);
int p = get_par(r);
// er(r, p);
int tmp;
cnt_sub.upd(st[r], tmp = -cnt_sub.get(st[r], st[r] + 1));
cnt_sub.upd(st[p], -tmp);
sum_val.upd(st[r], -val[r]);
smul.upd(r, 1);
sum_val.upd(st[p], val[r]); val[p] += val[r], val[r] = 0;
int emp = cnt_sub.get(st[p], st[p] + 1);
// er(emp, val[p], C(val[p] + emp - 1, emp));
smul.upd(p, C(val[p] + emp - 1, val[p]));
};
int q; cin >> q;
cout << smul.get() << '\n';
while(q--){
int t; cin >> t;
if(t == 1){
int u, x; cin >> u >> x; u--;
add(u, x);
}else{
int u; cin >> u; u--;
rem(u);
}
cout << smul.get() << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
268 ms |
60620 KB |
Output is correct |
| 2 |
Correct |
256 ms |
60812 KB |
Output is correct |
| 3 |
Correct |
251 ms |
60616 KB |
Output is correct |
| 4 |
Correct |
272 ms |
60716 KB |
Output is correct |
| 5 |
Correct |
228 ms |
56652 KB |
Output is correct |
| 6 |
Correct |
106 ms |
20616 KB |
Output is correct |
| 7 |
Correct |
114 ms |
20308 KB |
Output is correct |
| 8 |
Correct |
107 ms |
20448 KB |
Output is correct |
| 9 |
Correct |
259 ms |
53012 KB |
Output is correct |
| 10 |
Correct |
305 ms |
52916 KB |
Output is correct |
| 11 |
Correct |
253 ms |
53004 KB |
Output is correct |
| 12 |
Correct |
246 ms |
51276 KB |
Output is correct |
| 13 |
Correct |
227 ms |
57316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
105 ms |
19916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
277 ms |
61456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
448 ms |
110808 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
268 ms |
60620 KB |
Output is correct |
| 2 |
Correct |
256 ms |
60812 KB |
Output is correct |
| 3 |
Correct |
251 ms |
60616 KB |
Output is correct |
| 4 |
Correct |
272 ms |
60716 KB |
Output is correct |
| 5 |
Correct |
228 ms |
56652 KB |
Output is correct |
| 6 |
Correct |
106 ms |
20616 KB |
Output is correct |
| 7 |
Correct |
114 ms |
20308 KB |
Output is correct |
| 8 |
Correct |
107 ms |
20448 KB |
Output is correct |
| 9 |
Correct |
259 ms |
53012 KB |
Output is correct |
| 10 |
Correct |
305 ms |
52916 KB |
Output is correct |
| 11 |
Correct |
253 ms |
53004 KB |
Output is correct |
| 12 |
Correct |
246 ms |
51276 KB |
Output is correct |
| 13 |
Correct |
227 ms |
57316 KB |
Output is correct |
| 14 |
Incorrect |
105 ms |
19916 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
