//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 = 5e5 + 10, MOD = 1e9 + 7;
const ll INF = 1e18 + 100;
int n , r ,q , fact[maxn] , ans = 1, sub[maxn] , num[maxn] , sham[maxn];
vector<int> adj[maxn];
int is[maxn];
ll Power(ll x , ll y){
if(y < 0 or x < 0) return 0;
if(y == 0) return 1;
ll tmp = Power(x , y/2);
tmp = 1ll * tmp * tmp % MOD;
if(y&1) tmp = 1ll * x * tmp % MOD;
return tmp % MOD;
}
ll tarkib(int x , int y){
if(x == 0 or x == y) return 1;
if(x > y) return 0;
ll zir = fact[x] * fact[y-x] % MOD;
ll res = 1ll * fact[y] * Power(zir , MOD-2);
return res%MOD;
}
void Pre(int v = 1 , int p = 0){
sub[v] = 1;
for(int u : adj[v]) {
if(u != p){
Pre(u , v);
sub[v] += sub[u];
}
}
}
void Dfs(int v , int p){
int sum = 0;
for(int u : adj[v]){
if(u == p) continue;
Dfs(u , v);
if(ans == 0) return;
sum += num[u];
sham[v] += sham[u];
}
if(is[v] != -1){
if(is[v] < sum) {
ans = 0;
return;
}
ans = (ans * tarkib(sub[v] - sham[v] - 1 , is[v] - sum + sub[v] - sham[v] - 1)) % MOD;
int x = ans;
num[v] = is[v];
sham[v] = sub[v];
}
else num[v] = sum;
}
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;
memset(is , -1 , sizeof is);
cin >> n >> r;
is[1] = r;
for(int i = 1 ; i <= n-1 ; i++){
int u , v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
Pre();
cin >> q;
while(q--){
int ty;
cin >> ty;
memset(sham , 0 , sizeof sham);
memset(num , 0 , sizeof num);
ans = 1;
Dfs(1 , 0);
cout << ans << '\n';
if(ty == 1){
int v , w;
cin >> v >> w;
is[v] = w;
}
else{
int v;
cin >> v;
is[v] = -1;
}
}
memset(sham , 0 , sizeof sham);
memset(num , 0 , sizeof num);
ans = 1;
Dfs(1 , 0);
cout << ans << '\n';
}
Compilation message
Main.cpp: In function 'void Dfs(long long int, long long int)':
Main.cpp:63:13: warning: unused variable 'x' [-Wunused-variable]
63 | int x = ans;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
105 ms |
46672 KB |
Output is correct |
2 |
Correct |
96 ms |
46672 KB |
Output is correct |
3 |
Correct |
99 ms |
46880 KB |
Output is correct |
4 |
Correct |
102 ms |
46684 KB |
Output is correct |
5 |
Correct |
83 ms |
41812 KB |
Output is correct |
6 |
Correct |
11 ms |
30044 KB |
Output is correct |
7 |
Correct |
10 ms |
29788 KB |
Output is correct |
8 |
Correct |
10 ms |
29628 KB |
Output is correct |
9 |
Correct |
93 ms |
39244 KB |
Output is correct |
10 |
Correct |
86 ms |
39108 KB |
Output is correct |
11 |
Correct |
90 ms |
38996 KB |
Output is correct |
12 |
Correct |
83 ms |
38740 KB |
Output is correct |
13 |
Correct |
103 ms |
46120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
29532 KB |
Output is correct |
2 |
Correct |
11 ms |
29680 KB |
Output is correct |
3 |
Correct |
22 ms |
29532 KB |
Output is correct |
4 |
Correct |
16 ms |
29532 KB |
Output is correct |
5 |
Correct |
134 ms |
29532 KB |
Output is correct |
6 |
Correct |
293 ms |
29828 KB |
Output is correct |
7 |
Correct |
322 ms |
29820 KB |
Output is correct |
8 |
Correct |
306 ms |
29784 KB |
Output is correct |
9 |
Correct |
525 ms |
30032 KB |
Output is correct |
10 |
Correct |
546 ms |
29968 KB |
Output is correct |
11 |
Correct |
604 ms |
29788 KB |
Output is correct |
12 |
Correct |
54 ms |
29904 KB |
Output is correct |
13 |
Correct |
672 ms |
30152 KB |
Output is correct |
14 |
Correct |
667 ms |
30044 KB |
Output is correct |
15 |
Correct |
755 ms |
30120 KB |
Output is correct |
16 |
Correct |
566 ms |
29788 KB |
Output is correct |
17 |
Correct |
618 ms |
29892 KB |
Output is correct |
18 |
Correct |
530 ms |
30052 KB |
Output is correct |
19 |
Correct |
565 ms |
30140 KB |
Output is correct |
20 |
Correct |
261 ms |
29816 KB |
Output is correct |
21 |
Correct |
251 ms |
29812 KB |
Output is correct |
22 |
Correct |
70 ms |
29532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3058 ms |
45916 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3012 ms |
39504 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
105 ms |
46672 KB |
Output is correct |
2 |
Correct |
96 ms |
46672 KB |
Output is correct |
3 |
Correct |
99 ms |
46880 KB |
Output is correct |
4 |
Correct |
102 ms |
46684 KB |
Output is correct |
5 |
Correct |
83 ms |
41812 KB |
Output is correct |
6 |
Correct |
11 ms |
30044 KB |
Output is correct |
7 |
Correct |
10 ms |
29788 KB |
Output is correct |
8 |
Correct |
10 ms |
29628 KB |
Output is correct |
9 |
Correct |
93 ms |
39244 KB |
Output is correct |
10 |
Correct |
86 ms |
39108 KB |
Output is correct |
11 |
Correct |
90 ms |
38996 KB |
Output is correct |
12 |
Correct |
83 ms |
38740 KB |
Output is correct |
13 |
Correct |
103 ms |
46120 KB |
Output is correct |
14 |
Correct |
10 ms |
29532 KB |
Output is correct |
15 |
Correct |
11 ms |
29680 KB |
Output is correct |
16 |
Correct |
22 ms |
29532 KB |
Output is correct |
17 |
Correct |
16 ms |
29532 KB |
Output is correct |
18 |
Correct |
134 ms |
29532 KB |
Output is correct |
19 |
Correct |
293 ms |
29828 KB |
Output is correct |
20 |
Correct |
322 ms |
29820 KB |
Output is correct |
21 |
Correct |
306 ms |
29784 KB |
Output is correct |
22 |
Correct |
525 ms |
30032 KB |
Output is correct |
23 |
Correct |
546 ms |
29968 KB |
Output is correct |
24 |
Correct |
604 ms |
29788 KB |
Output is correct |
25 |
Correct |
54 ms |
29904 KB |
Output is correct |
26 |
Correct |
672 ms |
30152 KB |
Output is correct |
27 |
Correct |
667 ms |
30044 KB |
Output is correct |
28 |
Correct |
755 ms |
30120 KB |
Output is correct |
29 |
Correct |
566 ms |
29788 KB |
Output is correct |
30 |
Correct |
618 ms |
29892 KB |
Output is correct |
31 |
Correct |
530 ms |
30052 KB |
Output is correct |
32 |
Correct |
565 ms |
30140 KB |
Output is correct |
33 |
Correct |
261 ms |
29816 KB |
Output is correct |
34 |
Correct |
251 ms |
29812 KB |
Output is correct |
35 |
Correct |
70 ms |
29532 KB |
Output is correct |
36 |
Execution timed out |
3058 ms |
45916 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |