//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 3e5 + 10, MOD = 1e9 + 7;
const ll INF = 1e18 + 100;
int n , q , root , h[maxn] , st[maxn] , fn[maxn] , ti , val[maxn] , fact[maxn] , sub[maxn] , ans;
vector<int> adj[maxn];
void Dfs(int v , int p){
st[v] = ++ti , h[v] = h[p]+1;
for(int u : adj[v]) if(u != p) Dfs(u , v) , sub[v] += sub[u];
sub[v] += adj[v].size();
if(v != 1) sub[v]--;
fn[v] = ti;
}
int Power(int x , int y){
if(y == 0) return 1;
int tmp = Power(x , y/2);
tmp = tmp * tmp % MOD;
if(y & 1) tmp = tmp * x % MOD;
return tmp;
}
int Sayale(int x , int y){ // paeen bala
return fact[x+y] * Power(fact[x] * fact[y] % MOD , MOD-2) % MOD;
}
struct FindPar{
set<pii , greater<pii>> hoom[4*maxn];
void Update(int id , int L , int R , int l , int r , int w , int ty){
if(L == l and R == r) {
if(ty == 0) hoom[id].erase({h[w] , w});
else hoom[id].insert({h[w] , w});
return;
}
int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
if(l < mid) Update(lc , L , mid , l , min(r, mid) , w , ty);
if(r > mid) Update(rc , mid , R , max(l , mid) , r , w , ty);
}
int Get(int id , int L , int R , int idx , int v){
int res = 0;
if(hoom[id].size()) res = hoom[id].begin()->S;
if(L + 1 == R) return res;
int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1 , res2;
if(idx < mid) res2 = Get(lc , L , mid , idx , v);
else res2 = Get(rc , mid , R , idx , v);
return h[res] > h[res2] ? res : res2;
}
}Find;
struct Segment{
int toop[4*maxn] , sabad[4*maxn]; // barchasb - raas
void Update(int id , int L , int R , int idx , int w , int ty){ // ty = 0 -> toop , ty = 1 -> sabad
if(L+1 == R){
ty == 0 ? toop[id] += w : sabad[id] += w;
return;
}
int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
if(idx < mid) Update(lc , L , mid , idx , w , ty);
else Update(rc , mid , R , idx , w , ty);
toop[id] = toop[lc] + toop[rc];
sabad[id] = sabad[lc] + sabad[rc];
}
pii Get(int id , int L , int R , int l , int r){
if(L == l and R == r) return{toop[id] , sabad[id]};
int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
pii res1 = {0,0} , res2 = {0 , 0};
if(l < mid) res1 = Get(lc , L , mid , l , min(r , mid));
if(r > mid) res2 = Get(rc , mid , R , max(l , mid) , r);
return {res1.F + res2.F , res1.S + res2.S};
}
}Seg;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
fact[0] = 1;
for(int i = 1 ; i < maxn ; i++) fact[i] = fact[i-1] * i % MOD;
cin >> n >> root;
for(int i = 1 ; i < n ; i++){
int u , v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
Dfs(1 , 0);
cin >> q;
ans = Sayale(sub[1] , root);
val[1] = root;
cout << ans << '\n';
Find.Update(1 , 1 , n+1 , st[1] , fn[1]+1 , 1 , 1);
Seg.Update(1 , 1 , n+1 , st[1] , root , 0);
Seg.Update(1 , 1 , n+1 , st[1] , sub[1] , 1);
while(q--){
int ty , v , w;
cin >> ty;
if(ans <= 0) ans = 1;
if(ty == 1){
cin >> v >> w;
val[v] = w;
if(val[v] < 0){
ans = 0;
continue;
}
int par = Find.Get(1 , 1 , n+1 , st[v] , v);
pii x = Seg.Get(1 , 1 , n+1 , st[v] , fn[v]+1);
pii y = Seg.Get(1 , 1 , n+1 , st[par]+1 , fn[par]+1);
ans = ans * Power(Sayale(sub[par]-y.S , val[par]-y.F) , MOD-2) % MOD;
ans = ans * Sayale(sub[v] - x.S , val[v]-x.F) % MOD;
Seg.Update(1 , 1 , n+1 , st[v] , val[v] - x.F , 0);
Seg.Update(1 , 1 , n+1 , st[v] , sub[v] - x.S + 1 , 1);
y = Seg.Get(1 , 1 , n+1 , st[par]+1 , fn[par]+1);
ans = ans * Sayale(sub[par]-y.S , val[par]-y.F) % MOD;
Find.Update(1 , 1 , n+1 , st[v] , fn[v]+1 , v , 1);
}
else{
cin >> v;
int par = Find.Get(1 , 1 , n+1 , st[v]-1 , v);
pii x = Seg.Get(1 , 1 , n+1 , st[v]+1 , fn[v]+1);
pii y = Seg.Get(1 , 1 , n+1 , st[par]+1 , fn[par]+1);
ans = ans * Power(Sayale(sub[v]-x.S, val[v]-x.F) , MOD-2) % MOD;
ans = ans * Power(Sayale(sub[par]-y.S , val[par]-y.F) , MOD-2) % MOD;
Seg.Update(1 , 1 , n+1 , st[v] , -(sub[v] - x.F + 1) , 1);
Seg.Update(1 , 1 , n+1 , st[v] , -(val[v] - x.S) , 0);
val[v] = 0;
y = Seg.Get(1 , 1 , n+1 , st[par]+1 , fn[par]+1);
ans = ans * Sayale(sub[par]-y.S , val[par]-y.F) % MOD;
Find.Update(1 , 1 , n+1 , st[v] , fn[v]+1 , v , 0);
}
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
103 ms |
93264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
70236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
195 ms |
194092 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
293 ms |
189432 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
103 ms |
93264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
