#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define fi first #define se second #define vi vector<int> #define vll vector<long long> #define pii pair<int, int> #define pll pair<long long, long long> #define pb push_back #define mp make_pair #define eb emplace_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count()); inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);} inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);} #ifdef DEBUG auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";} #define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X) #else #define debug(...){} #endif struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; struct pair_hash{ size_t operator()(const pair<int,int>&x)const{ return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32)); } }; const int MOD = 1e9 + 7; const int MAXN = 3e5 + 7; const int BASE = (1 << 19); vi g[MAXN]; int parent[MAXN]; ll A[MAXN]; int tin[MAXN]; int tout[MAXN]; int id[MAXN]; int treeSpecial[2 * BASE + 7]; int treeSizes[2 * BASE + 7]; ll treeValues[2 * BASE + 7]; ll fact[2 * MAXN]; ll factInv[2 * MAXN]; int timer = 0; int siz[MAXN]; int n, q; void dfs(int v, int p){ parent[v] = p; id[timer] = v; tin[v] = timer++; siz[v] = 1; for(auto u : g[v]){ if(u == p){ continue; } dfs(u, v); siz[v] += siz[u]; } tout[v] = timer - 1; } void updSpecial(int v){ v = tin[v]; v += BASE; if(treeSpecial[v] == 0){ treeSpecial[v] = tout[id[v - BASE]]; }else{ treeSpecial[v] = 0; } v /= 2; while(v > 0){ treeSpecial[v] = max(treeSpecial[2 * v], treeSpecial[2 * v + 1]); v /= 2; } } int findAncestor(int v, int l, int p, int x){ if(treeSpecial[v] < tin[x] || l > tin[x]){ return -1; } if(l == p){ return id[v - BASE]; } int mid = (l + p) / 2; int r = findAncestor(2 * v + 1, mid + 1, p, x); if(r != -1){ return r; } return findAncestor(2 * v, l, mid, x); } int getAnc(int v){ return findAncestor(1, 0, BASE - 1, v); } ll inv(ll a){ if(a <= 1LL){ return a; } return (ll)MOD - (ll)(MOD / a) * inv(MOD % a) % MOD; } void preprocessing(){ dfs(1, 0); updSpecial(1); fact[0] = 1LL; for(int i = 1; i < 2 * MAXN; i++){ fact[i] = (ll)fact[i - 1] * i; fact[i] %= MOD; } factInv[2 * MAXN - 1] = inv(fact[2 * MAXN - 1]); for(int i = 2 * MAXN - 1; i >= 1; i--){ factInv[i - 1] = (ll)factInv[i] * i % MOD; } } ll calc(int N, int k){ if(N < k){ return 0LL; } return (ll)fact[N] * ((ll)factInv[N - k] * factInv[k] % MOD) % MOD; } void updSubtreeSize(int v, int val){ if(v == 0){ return; } v = tin[v]; v += BASE; while(v > 0){ treeSizes[v] += val; v /= 2; } } int querySubtreeSize(int v, int l, int p, int a, int b){ if(p < a || b < l){ return 0; } if(a <= l && p <= b){ return treeSizes[v]; } int mid = (l + p) / 2; return querySubtreeSize(2 * v, l, mid, a, b) + querySubtreeSize(2 * v + 1, mid + 1, p, a, b); } int getSubtreeSize(int v){ return siz[v] - querySubtreeSize(1, 0, BASE - 1, tin[v], tout[v]); } void updValue(int v, ll val){ if(v == 0){ return; } v = tin[v]; v += BASE; while(v > 0){ treeValues[v] += val; v /= 2; } } ll querySubtreeValues(int v, int l, int p, int a, int b){ if(p < a || b < l){ return 0LL; } if(a <= l && p <= b){ return treeValues[v]; } int mid = (l + p) / 2; return (ll)querySubtreeValues(2 * v, l, mid, a, b) + querySubtreeValues(2 * v + 1, mid + 1, p, a, b); } ll getSubtreeVal(int v){ return querySubtreeValues(1, 0, BASE - 1, tin[v], tout[v]); } ll ans; int cntZeros = 0; void deleteSubtree(int v){ // cerr << "DELETING: " << v << ' ' << ans << '\n'; ll s = getSubtreeVal(v); int sajz = getSubtreeSize(v); //cerr << "VAL: " << s << " SAJZ: " << sajz << '\n'; if(s > A[v]){ // cerr << "ZERO\n"; cntZeros--; }else{ // cerr << calc(A[v] - s + sajz - 1, sajz - 1) << '\n'; ans = (ll)ans * inv(calc(A[v] - s + sajz - 1, sajz - 1)) % MOD; } } void addSubtree(int v){ // cerr << "ADDING: " << v << ' ' << ans << '\n'; ll s = getSubtreeVal(v); int sajz = getSubtreeSize(v); // cerr << "VAL: " << s << " SAJZ: " << sajz << '\n'; if(s > A[v]){ // cerr << "ZERO\n"; cntZeros++; }else{ // cerr << calc(A[v] - s + sajz - 1, sajz - 1) << '\n'; ans = (ll)ans * calc(A[v] - s + sajz - 1, sajz - 1) % MOD; } } void addTag(int v, int r){ int x = getAnc(v); deleteSubtree(x); updSpecial(v); A[v] = r; int sajz = getSubtreeSize(v); // cerr << sajz << '\n'; updSubtreeSize(parent[v], sajz); updSubtreeSize(parent[x], -sajz); ll val = getSubtreeVal(v); updValue(parent[v], r - val); updValue(parent[x], val - r); addSubtree(v); addSubtree(x); } void deleteTag(int v){ updSpecial(v); int x = getAnc(v); deleteSubtree(x); deleteSubtree(v); int sajz = getSubtreeSize(v); updSubtreeSize(parent[v], -sajz); updSubtreeSize(parent[x], sajz); ll val = getSubtreeVal(v); updValue(parent[v], val - A[v]); updValue(parent[x], A[v] - val); A[v] = 0LL; addSubtree(x); } int main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin >> n >> A[1]; for(int i = 2; i <= n; i++){ A[i] = 0LL; int a, b; cin >> a >> b; g[a].pb(b); g[b].pb(a); } preprocessing(); cin >> q; ans = calc(n + A[1] - 1, n - 1); cout << ans << '\n'; while(q--){ int type; cin >> type; if(type == 1){ int v, r; cin >> v >> r; addTag(v, r); }else{ int v; cin >> v; deleteTag(v); } if(cntZeros){ cout << "0\n"; }else{ cout << ans << '\n'; } // cerr << "========\n"; } return 0; }