#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) (x).size();
#define F first
#define S second
#define lc id << 1
#define rc lc | 1
int Pow(int a, int b, int md, int ret = 1) {
for (; b; b >>= 1, a = 1ll * a * a % md)
if (b & 1) ret = 1ll * ret * a % md;
return ret;
}
const int N = 5e5 + 10, MOD = 1e9 + 7;
int F[N], St[N], Ft[N], I[N], hv[N], hd[N], S[N], P[N], val[N], H[N], n, q, r, timer;
vector<int> adj[N]; int seg[N << 2], lz[N << 2]; set<pii> st[N]; int ret;
void shift(int id, int l, int r) {
seg[id] += lz[id];
if (r - l > 1)
lz[lc] += lz[id], lz[rc] += lz[id];
lz[id] = 0;
}
void upd(int ql, int qr, int x, int id = 1, int l = 0, int r = n) {
shift(id, l, r);
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) { lz[id] += x; return shift(id, l, r); }
int md = (l + r) >> 1;
upd(ql, qr, x, lc, l, md), upd(ql, qr, x, rc, md, r);
seg[id] = min(seg[lc], seg[rc]);
}
int get(int p, int id = 1, int l = 0, int r = n) {
shift(id, l, r);
if (r - l < 2) { return seg[id]; }
int md = (l + r) >> 1;
return p < md ? get(p, lc, l, md) : get(p, rc, md, r);
}
void preDFS(int v, int p = -1) {
S[v] = 1; P[v] = p;
for (int u : adj[v])
if (u != p) { H[u] = H[v] + 1, preDFS(u, v), S[v] += S[u];
if (S[hv[v]] < S[u]) hv[v] = u; }
}
void hldDFS(int v, int p = -1) {
if (!~p) hd[v] = v;
St[v] = timer++;
if (hv[v])
hd[hv[v]] = hd[v], hldDFS(hv[v], v);
for (int u : adj[v])
if (u != p && u != hv[v])
hldDFS(hd[u] = u, v);
Ft[v] = timer;
}
int C(int x, int y) {
if (x < y || y < 0) return 0;
return F[x] * 1ll * I[y] * I[x - y] % MOD;
}
int main() {
scanf("%d%d", &n, &r);
F[0] = 1; st[1].insert(pii(0, 1)); val[1] = r;
for (int i = 1; i < N; i++)
F[i] = 1ll * F[i - 1] * i % MOD;
I[N - 1] = Pow(F[N - 1], MOD - 2, MOD);
for (int i = N - 1; i; i--)
I[i - 1] = 1ll * I[i] * i % MOD;
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
preDFS(1); hldDFS(1);
printf("%d\n", ret = C(r + n - 1, n - 1));
for (int i = 1; i <= n; i++)
upd(St[i], St[i] + 1, S[i]);
for (scanf("%d", &q); q; q--) {
int t, v, x; scanf("%d%d", &t, &v);
if (t < 2) {
scanf("%d", &x); int sub = get(St[v]);
ret = 1ll * ret * C((val[v] = x) + sub - 1, sub - 1) % MOD;
int u = P[v];
while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[v]) {
upd(St[hd[u]], St[u] + 1, -sub);
u = P[hd[u]];
}
int pr = prev(st[hd[u]].lower_bound(pii(St[v], -1)))->S;
st[hd[v]].insert(pii(St[v], v));
int cpr = get(St[pr]); ret = 1ll * ret * Pow(C(cpr - 1 + val[pr], val[pr]), MOD - 2, MOD) % MOD;
upd(St[pr], St[u] + 1, -sub); cpr = get(St[pr]);
ret = 1ll * ret * C(cpr - 1 + val[pr], val[pr]) % MOD;
} else {
int sub = get(St[v]);
ret = 1ll * ret * Pow(C(sub + val[v] - 1, val[v]), MOD - 2, MOD) % MOD;
int u = P[v]; st[hd[v]].erase(pii(St[v], v));
while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[v]) {
upd(St[hd[u]], St[u] + 1, sub);
u = P[hd[u]];
}
int pr = prev(st[hd[u]].lower_bound(pii(St[v], -1)))->S;
int cpr = get(St[pr]); ret = 1ll * ret * Pow(C(cpr - 1 + val[pr], val[pr]), MOD - 2, MOD) % MOD;
upd(St[pr], St[u] + 1, sub); cpr = get(St[pr]);
ret = 1ll * ret * C(cpr - 1 + val[pr], val[pr]) % MOD;
}
printf("%d\n", ret);
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d%d", &n, &r);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | int u, v; scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:86:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | for (scanf("%d", &q); q; q--) {
| ~~~~~^~~~~~~~~~
Main.cpp:87:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | int t, v, x; scanf("%d%d", &t, &v);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:89:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | scanf("%d", &x); int sub = get(St[v]);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
322 ms |
66496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
39412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
350 ms |
66992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
631 ms |
116796 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
322 ms |
66496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
