//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];
vector<int> adj[maxn];
void Dfs(int v , int p){
st[v] = ++ti , h[v] = h[p]+1 , sub[v] = 1;
for(int u : adj[v]) if(u != p) Dfs(u , v) , sub[v] += sub[u];
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
if(y == 0) return 1;
if(y < 0) return 0;
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 Sum_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])%MOD;
sabad[id] = (sabad[lc] + sabad[rc])%MOD;
}
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)%MOD , (res1.S + res2.S)%MOD};
}
}Seg;
struct Ans{
int res[4*maxn];
Ans(){
memset(res , -1 , sizeof res);
}
void Merge(int id , int lc , int rc){
if(res[lc] == -1 and res[rc] == -1) res[id] = -1;
else if(res[lc] == -1) res[id] = res[rc];
else if(res[rc] == -1) res[id] = res[lc];
else res[id] = res[lc] * res[rc] % MOD;
return;
}
void Update(int id , int L , int R , int idx , int w){
if(L+1 == R){
res[id] = w;
return;
}
int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
if(idx < mid) Update(lc , L , mid , idx , w);
else Update(rc , mid , R , idx , w);
Merge(id , lc , rc);
}
}Ans;
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.Update(1 , 1 , n+1 , 1 , Sayale(sub[1]-1 , root));
val[1] = root;
cout << Ans.res[1] << '\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(ty == 1){
cin >> v >> w;
val[v] = w;
int par = Find.Get(1 , 1 , n+1 , st[v] , v);
pii x = Seg.Get(1 , 1 , n+1 , st[v] , fn[v]+1);
Ans.Update(1 , 1 , n+1 , st[v] , Sayale(sub[v]-x.S-1 , val[v]-x.F));
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);
Seg.Update(1 , 1 , n+1 , st[par] , -(sub[v] - x.S) , 1);
Seg.Update(1 , 1 , n+1 , st[par] , -(val[v] - x.F) , 0);
pii y = Seg.Get(1 , 1 , n+1 , st[par]+1 , fn[par]+1);
Ans.Update(1 , 1 , n+1 , st[par] , Sayale(sub[par]-y.S-1 , val[par]-y.F));
Find.Update(1 , 1 , n+1 , st[v] , fn[v]+1 , v , 1);
}
else{
cin >> v;
Find.Update(1 , 1 , n+1 , st[v] , fn[v]+1 , v , 0);
int par = Find.Get(1 , 1 , n+1 , st[v] , v);
pii x = Seg.Get(1 , 1 , n+1 , st[v]+1 , fn[v]+1);
Ans.Update(1 , 1 , n+1 , st[v] , -1);
Seg.Update(1 , 1 , n+1 , st[v] , -(sub[v] - x.S) , 1);
Seg.Update(1 , 1 , n+1 , st[v] , -(val[v] - x.F) , 0);
Seg.Update(1 , 1 , n+1 , st[par] , sub[v]-x.S , 1);
Seg.Update(1 , 1 , n+1 , st[par] , val[v]-x.F , 0);
val[v] = 0;
pii y = Seg.Get(1 , 1 , n+1 , st[par]+1 , fn[par]+1);
Ans.Update(1 , 1 , n+1 , st[par] , Sayale(sub[par]-y.S-1 , val[par]-y.F));
Find.Update(1 , 1 , n+1 , st[v] , fn[v]+1 , v , 0);
}
cout << Ans.res[1] <<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
100436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
80472 KB |
Output is correct |
| 2 |
Runtime error |
1498 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
163 ms |
113944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
734 ms |
108776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
100436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
