#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; ll sil[600001]; ll odwsil[600001]; ll P(ll x) { ll ans = 1; rep(bit,31) { if((MOD-2)&(1<<bit)) { ans = (ans*x)%MOD; } x = (x*x)%MOD; } return ans; } ll calc(int n, int k) { if(k == 0) return 1; return (((sil[n+k-1]*odwsil[n-1])%MOD)*odwsil[k])%MOD; } vi graph[200001]; int pre[200001]; int maxpre[200001]; int preind[200001]; int jump_hld[200001]; int jump[200001]; int sub[200001]; int lim[200001]; set<int> active[200001]; int bad_cnt = 0; int cur_pre = 1; const int tree_siz = 1024*512-1; pll sum[tree_siz+1]; void add_val(int p, pll x) { int v = (tree_siz/2+1+p); while(true) { sum[v].ff += x.ff; sum[v].ss += x.ss; if(v != 1) v /= 2; else break; } } pll get_sum(int akt, int p1, int p2, int s1, int s2) { if(p2 < s1 || p1 > s2) return {0,0}; if(p1 >= s1 && p2 <= s2) { return sum[akt]; } pll w1 = get_sum(akt*2,p1,(p1+p2)/2,s1,s2); pll w2 = get_sum(akt*2+1,(p1+p2)/2+1,p2,s1,s2); return {w1.ff+w2.ff,w1.ss+w2.ss}; } void dfs_sub(int v, int pop) { sub[v] = 1; forall(it,graph[v]) { if(it != pop) { dfs_sub(it,v); sub[v] += sub[it]; } } } void dfs(int v, int pop, int c) { jump_hld[v] = c; jump[v] = pop; pii best = {-1,-1}; pre[v] = cur_pre++; maxpre[v] = pre[v]; preind[pre[v]] = v; forall(it,graph[v]) { if(it != pop) best = max(best,{sub[it],it}); } if(best.ss == -1) return; dfs(best.ss,v,c); maxpre[v] = maxpre[best.ss]; forall(it,graph[v]) { if(it != pop && it != best.ss) { dfs(it,v,it); maxpre[v] = maxpre[it]; } } } ll ans = 1; pll get_val(int v) { pll val = {0,0}; if(pre[v] != maxpre[v]) val = get_sum(1,0,tree_siz/2,pre[v]+1,maxpre[v]); val.ff = sub[v]-val.ff; return val; } void query(int v, ll lm) { pll val = get_val(v); if(lim[v] != -1) { if(lim[v]-val.ss >= 0) { ans = (ans*P(calc(val.ff,lim[v]-val.ss)))%MOD; } else bad_cnt--; } int cur = jump[v]; int nxt_v = -1; while(cur != 0) { int r = jump_hld[cur]; if(siz(active[r]) == 0 || *active[r].begin() > pre[cur]) { cur = jump[r]; continue; } else { auto nxt = active[r].upper_bound(pre[cur]); nxt--; int v2 = preind[*nxt]; nxt_v = v2; pll val2 = get_val(v2); if(lim[v2]-val2.ss >= 0) { ans = (ans*P(calc(val2.ff,lim[v2]-val2.ss)))%MOD; } else bad_cnt--; if(lim[v] == -1) { val2.ff -= val.ff; val2.ss -= val.ss; val2.ss += lm; } else { val2.ss -= lim[v]; if(lm != -1) val2.ss += lm; else { val2.ss += val.ss; val2.ff += val.ff; } } if(lim[v2]-val2.ss >= 0) { ans = (ans*calc(val2.ff,lim[v2]-val2.ss))%MOD; } else bad_cnt++; break; } } active[jump_hld[v]].insert(pre[v]); if(lm == -1) active[jump_hld[v]].erase(pre[v]); if(lim[v] == -1) { add_val(pre[v],{val.ff,-val.ss+lm}); if(nxt_v != -1) add_val(pre[nxt_v],{-val.ff,+val.ss-lm}); } else { if(lm != -1) { add_val(pre[v],{0,-lim[v]+lm}); if(nxt_v != -1) add_val(pre[nxt_v],{0,lim[v]-lm}); } else { add_val(pre[v],{-val.ff,val.ss-lim[v]}); if(nxt_v != -1) add_val(pre[nxt_v],{val.ff,-val.ss+lim[v]}); } } lim[v] = lm; if(lim[v] != -1) { if(lim[v]-val.ss >= 0) { ans = (ans*calc(val.ff,lim[v]-val.ss))%MOD; } else bad_cnt++; } } ll get_ans() { if(bad_cnt == 0) return ans; return 0; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); sil[0] = 1; odwsil[0] = 1; rep2(i,1,600000) { sil[i] = (sil[i-1]*i)%MOD; odwsil[i] = P(sil[i]); } int n,r; cin >> n >> r; rep2(i,1,n) lim[i] = -1; rep(i,n-1) { int a,b; cin >> a >> b; graph[a].pb(b); graph[b].pb(a); } dfs_sub(1,1); dfs(1,0,1); query(1,r); cout << get_ans() << "\n"; int q; cin >> q; rep(qq,q) { int t; cin >> t; if(t == 1) { int v,u; cin >> v >> u; query(v,u); } else { int v; cin >> v; query(v,-1); } cout << get_ans() << "\n"; } }