#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 roz[200007]; long long gl[200007]; long long gora[200007]; long long poz[200007]; long long odw2[200007]; long long gleb[200007]; long long cz2 = 0; set<long long> secik; 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; } void dfs1(long long cur, long long pop) { roz[cur] = 1; gl[cur] = 0; for(auto x : graph[cur]) { if(x != pop) { gleb[x] = gleb[cur] + 1; dfs1(x, cur); roz[cur] += roz[x]; if(gl[cur] == 0 || roz[x] > roz[gl[cur]]) { gl[cur] = x; } } } } void dfs2(long long cur, long long curg) { gora[cur] = curg; cz2++; poz[cur] = cz2; odw2[cz2] = cur; if(gl[cur] != 0) { dfs2(gl[cur], curg); } for(auto x : graph[cur]) { if(x != ojc[cur] && x != gl[cur]) { dfs2(x, x); } } } long long znajdz(long long x) { while(x != 0) { auto it = secik.upper_bound(poz[x]); if(it != secik.begin()) { it--; if(*it >= poz[gora[x]]) { return odw2[*it]; } } x = ojc[gora[x]]; } return 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); 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); gleb[1] = 0; dfs1(1, 0); dfs2(1, 1); secik.insert(poz[1]); 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); secik.erase(poz[b]); war[b] = -1; b = znajdz(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; secik.insert(poz[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); //cout << odp[b] << endl; b = znajdz(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; }