#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 3e5 + 5, mod = 1e9 + 7; // !
int tmout[N], tmin[N], timer, ans, n, a[N], t_sz[N], t[N];
int p[N][25];
vector<int> V[N];
int fact[2 * N], invfact[2 * N], sz[N];
int pwr(int u, int v) {
int ans = 1;
while(v) {
if(v % 2) ans = ans * u % mod;
v /= 2;
u = u * u % mod;
}
return ans;
}
int C(int a, int b) {
if(a < b) return 0;
return fact[a] * invfact[b] % mod * invfact[a - b] % mod;
}
int sb(int a, int b) {
return C(a + b - 1, b - 1);
}
void dfs(int u,int P) {
tmin[u] = ++timer;
p[u][0] = P;
for(int i = 1; i < 19; i++) p[u][i] = p[p[u][i - 1]][i - 1];
for(int i = 0; i < V[u].size(); i++) {
if(V[u][i] == P) continue;
dfs(V[u][i], u);
sz[u] += sz[V[u][i]];
}
++sz[u];
tmout[u] = timer;
}
void upd_sz(int id, int val) {
for(id; id >= 1; id -= id & (-id)) t_sz[id] += val;
}
int get_sz(int id) {
int ans = 0;
for(id; id <= n; id += id & (-id)) ans += t_sz[id];
return ans;
}
void upd(int id, int val) {
for(id; id >= 1; id -= id & (-id)) t[id] += val;
}
int get(int id) {
int ans = 0;
for(id; id <= n; id += id & (-id)) ans += t[id];
return ans;
}
int up(int u) {
for(int i = 18; i >= 0; i--) {
// ramdeni mshobelia monishnuli
if(p[u][i] && get(tmin[p[u][i]]) == get(tmin[u])) u = p[u][i];
}
return u;
}
void add(int u, int v) {
a[u] = v;
int p = up(u);
upd(tmout[u], 1); upd(tmin[u] - 1, -1);
int SZ_p = sz[p] - (get_sz(tmin[p] + 1) - get_sz(tmout[p] + 1));
int SZ = sz[u] - (get_sz(tmin[u] + 1) - get_sz(tmout[u] + 1));
upd_sz(tmin[u], -SZ);
upd_sz(tmin[p], SZ);
ans = ans * pwr(sb(a[p], SZ_p), mod - 2) % mod * sb(a[p], SZ_p - SZ) % mod * sb(a[u], SZ) % mod;
}
void rem(int u) {
upd(tmout[u], -1); upd(tmin[u] - 1, 1);
int p = up(u);
int SZ = sz[u] - (get_sz(tmin[u] + 1) - get_sz(tmout[u] + 1));
upd_sz(tmin[u], SZ);
upd_sz(tmin[p], -SZ);
int SZ_p = sz[p] - (get_sz(tmin[p] + 1) - get_sz(tmout[p] + 1));
ans = ans * pwr(sb(a[p], SZ_p - SZ), mod - 2) % mod * pwr(sb(a[u], SZ) , mod - 2) % mod * sb( a[p], SZ_p) % mod;
}
main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> a[1];
for(int i = 2; i <= n; i++) {
int u, v;
cin >> u >> v;
V[u].push_back(v);
V[v].push_back(u);
}
dfs(1, 0);
fact[0] = invfact[0] = 1;
for(int i = 1; i <= N + n; i++) {
fact[i] = fact[i - 1] * i % mod;
invfact[i] = invfact[i - 1] * pwr(i, mod - 2) % mod;
}
ans = sb(a[1], n);
cout <<ans << endl;
int q;
cin >> q;
while(q--) {
int t;
cin >> t;
if(t == 1) {
int u, v;
cin >> u >> v;
add(u, v);
} else {
int u;
cin >> u;
rem(u);
}
cout << ans << endl;
}
}
Compilation message
Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:33:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'void upd_sz(long long int, long long int)':
Main.cpp:42:9: warning: statement has no effect [-Wunused-value]
42 | for(id; id >= 1; id -= id & (-id)) t_sz[id] += val;
| ^~
Main.cpp: In function 'long long int get_sz(long long int)':
Main.cpp:46:9: warning: statement has no effect [-Wunused-value]
46 | for(id; id <= n; id += id & (-id)) ans += t_sz[id];
| ^~
Main.cpp: In function 'void upd(long long int, long long int)':
Main.cpp:50:9: warning: statement has no effect [-Wunused-value]
50 | for(id; id >= 1; id -= id & (-id)) t[id] += val;
| ^~
Main.cpp: In function 'long long int get(long long int)':
Main.cpp:54:9: warning: statement has no effect [-Wunused-value]
54 | for(id; id <= n; id += id & (-id)) ans += t[id];
| ^~
Main.cpp: At global scope:
Main.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
85 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
325 ms |
72348 KB |
Output is correct |
| 2 |
Correct |
321 ms |
73380 KB |
Output is correct |
| 3 |
Correct |
331 ms |
73452 KB |
Output is correct |
| 4 |
Correct |
352 ms |
73416 KB |
Output is correct |
| 5 |
Correct |
249 ms |
70100 KB |
Output is correct |
| 6 |
Correct |
57 ms |
13000 KB |
Output is correct |
| 7 |
Correct |
64 ms |
12868 KB |
Output is correct |
| 8 |
Correct |
69 ms |
12856 KB |
Output is correct |
| 9 |
Correct |
373 ms |
69068 KB |
Output is correct |
| 10 |
Correct |
305 ms |
68656 KB |
Output is correct |
| 11 |
Correct |
330 ms |
68880 KB |
Output is correct |
| 12 |
Correct |
328 ms |
66048 KB |
Output is correct |
| 13 |
Correct |
323 ms |
67720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
12068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
450 ms |
149940 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
679 ms |
147232 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
325 ms |
72348 KB |
Output is correct |
| 2 |
Correct |
321 ms |
73380 KB |
Output is correct |
| 3 |
Correct |
331 ms |
73452 KB |
Output is correct |
| 4 |
Correct |
352 ms |
73416 KB |
Output is correct |
| 5 |
Correct |
249 ms |
70100 KB |
Output is correct |
| 6 |
Correct |
57 ms |
13000 KB |
Output is correct |
| 7 |
Correct |
64 ms |
12868 KB |
Output is correct |
| 8 |
Correct |
69 ms |
12856 KB |
Output is correct |
| 9 |
Correct |
373 ms |
69068 KB |
Output is correct |
| 10 |
Correct |
305 ms |
68656 KB |
Output is correct |
| 11 |
Correct |
330 ms |
68880 KB |
Output is correct |
| 12 |
Correct |
328 ms |
66048 KB |
Output is correct |
| 13 |
Correct |
323 ms |
67720 KB |
Output is correct |
| 14 |
Incorrect |
53 ms |
12068 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
