#include <bits/stdc++.h> using namespace std; vector<long long> graph[200007]; long long war[200007]; long long sil[500007]; long long odw[500007]; long long pre[200007]; long long post[200007]; long long ojc[200007]; long long odp[200007]; long long drz[1048580][2]; long long pot(long long liczba, long long wykladnik) { long long w = 1; while (wykladnik > 0) { if (wykladnik % 2 == 1) { w = (w * liczba) % 1000000007; } liczba = (liczba * liczba) % 1000000007; wykladnik /= 2; } return w; } long long cz = 0, zer = 0, wyn = 1; void dfs(long long cur, long long pop) { pre[cur] = cz; cz++; for(auto x : graph[cur]) { if(x != pop) { ojc[x] = cur; dfs(x, cur); } } post[cur] = cz; cz++; } void ustaw(long long gdzie, long long co, long long x) { gdzie += 524288; drz[gdzie][x] = co; gdzie /= 2; while(gdzie != 0) { //cout << gdzie << " " << co << " " << endl; drz[gdzie][x] = drz[2 * gdzie][x] + drz[2 * gdzie + 1][x]; gdzie /= 2; } } long long przedzial(long long curl, long long curr, long long l, long long r, long long cur, long long x) { if(l > curr || curl > r) { return 0; } else if(l <= curl && curr <= r) { //cout << cur << " " << curl << " " << curr << " " << l << " " << r << endl; return drz[cur][x]; } else { return przedzial(curl, (curl + curr) / 2, l, r, 2 * cur, x) + przedzial((curl + curr) / 2 + 1, curr, l, r, 2 * cur + 1, x); } } void policz(long long co) { if(odp[co] == 0) { zer--; } else if(odp[co] != -1) { wyn *= pot(odp[co], 1000000005); wyn %= 1000000007; } long long ilew = przedzial(0, 524287, pre[co] + 1, post[co], 1, 0) + 1; long long iles = war[co] - przedzial(0, 524287, pre[co] + 1, post[co], 1, 1); //cout << pre[co] << " " << post[co] << " " << ilew << " " << iles << endl; if(iles < 0) { zer++; odp[co] = 0; return; } odp[co] = (((sil[ilew + iles - 1] * odw[ilew - 1]) % 1000000007) * odw[iles]) % 1000000007; wyn *= odp[co]; wyn %= 1000000007; return; } int main() { sil[0] = 1; odw[0] = 1; for(long long i = 1; i <= 500005; i++) { sil[i] = sil[i - 1] * i; sil[i] %= 1000000007; } for(long long i = 1; i <= 500005; i++) { odw[i] = pot(sil[i], 1000000005); } long long n, r, q; cin >> n >> r; for(long long i = 0; i <= n; i++) { war[i] = -1; odp[i] = -1; } war[1] = r; odp[1] = (((sil[n + r - 1] * odw[n - 1]) % 1000000007) * odw[r]) % 1000000007; wyn = odp[1]; for(long long i = 0; i < n - 1; i++) { long long a, b; cin >> a >> b; graph[a].push_back(b); graph[b].push_back(a); } cin >> q; dfs(1, 0); for(long long i = 1; i <= n; i++) { ustaw(pre[i], 1, 0); //cout << pre[i] << endl; } cout << wyn << endl; while(q--) { long long a, b, c; cin >> a >> b; if(a == 2) { if(odp[b] == 0) { zer--; } else { wyn *= pot(odp[b], 1000000005); wyn %= 1000000007; } odp[b] = -1; ustaw(pre[b], 1, 0); ustaw(pre[b], 0, 1); war[b] = -1; while(war[b] == -1) { b = ojc[b]; } policz(b); ustaw(pre[b], -przedzial(0, 524287, pre[b] + 1, post[b], 1, 0), 0); ustaw(pre[b], -przedzial(0, 524287, pre[b] + 1, post[b], 1, 1) + war[b], 1); if(zer > 0) { cout << 0 << endl; } else { cout << wyn << endl; } } else { cin >> c; war[b] = c; policz(b); ustaw(pre[b], -przedzial(0, 524287, pre[b] + 1, post[b], 1, 0), 0); ustaw(pre[b], -przedzial(0, 524287, pre[b] + 1, post[b], 1, 1) + war[b], 1); //cout << odp[b] << endl; b = ojc[b]; while(war[b] == -1) { b = ojc[b]; } policz(b); ustaw(pre[b], -przedzial(0, 524287, pre[b] + 1, post[b], 1, 0), 0); ustaw(pre[b], -przedzial(0, 524287, pre[b] + 1, post[b], 1, 1) + war[b], 1); if(zer > 0) { cout << 0 << endl; } else { cout << wyn << endl; } } } return 0; }