#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int n;
ll mod;
vector<int> adj[N];
int h[N];
// segment tree
void modify(vector<int>& seg, int l, int r, ll v) {
int m = seg.size()/2;
r = min(r, m-1);
for (l += m, r += m+1; l < r; l /= 2, r/=2) {
if (l&1) {
seg[l] = ((ll)seg[l] * v)%mod;
l++;
}
if (r&1) {
r--;
seg[r] = ((ll)seg[r] * v)%mod;
}
}
}
int query(vector<int>& seg, int p) {
int res = 1;
int m = seg.size()/2;
for (p += m; p > 0; p /= 2) res = ((ll)res * (ll)seg[p])%mod;
return res;
}
// centroid decompostion
int sz[N], rem[N];
vector<tuple<int,int,int>> centroids[N];
vector<vector<int>> seg[N];
int dfsSz(int u, int p=-1) {
sz[u] = 1;
for (int v : adj[u]) {
if (rem[v] || v == p) continue;
sz[u] += dfsSz(v, u);
}
return sz[u];
}
int dfsCent(int u, int p, int totSz) {
for (int v : adj[u])
if (!rem[v] && v != p)
if (sz[v]*2 > totSz)
return dfsCent(v, u, totSz);
return u;
}
int dfs(int u, int p, int cent, int sub, int d) {
centroids[u].push_back({cent, sub, d});
int depth = 0;
for (int v : adj[u])
if (!rem[v] && v != p)
depth = max(depth, dfs(v, u, cent, sub, d + 1));
return depth + 1;
}
void handleCentroid(int u) {
int sub = 0;
int depth = 0;
for (int v : adj[u]) {
if (rem[v]) continue;
int subDepth = dfs(v, u, u, sub, 1);
depth = max(depth, subDepth+1);
sub++;
}
depth = min(depth, 40);
seg[u].resize(depth+1);
centroids[u].push_back({u, -1, 0});
for (int i=0; i<=depth; i++)
seg[u][i].assign((sub+2)*2, 1);
}
void centroidDecomposition(int u) {
dfsSz(u);
int cent = dfsCent(u, -1, sz[u]);
handleCentroid(cent);
rem[cent] = 1;
for (int v : adj[cent])
if (!rem[v])
centroidDecomposition(v);
}
// operations
const int SQ = 7;
void updateVertex(int u, int r, int v) {
for (auto p : centroids[u]) {
int cent, sub, d;
tie(cent, sub, d) = p;
int mx = min<int>(r-d+1, seg[cent].size());
for (int i=0; i<mx; i++) {
while (i + SQ < mx) i += SQ;
if (sub == -1) {
modify(seg[cent][i], 0, 1e9, v);
} else {
modify(seg[cent][i], 0, sub-1, v);
modify(seg[cent][i], sub+1, 1e9, v);
}
}
}
}
int queryVertex(int u) {
int res = 1;
auto add = [&](int x) {
res = ((ll)res * (ll)x)%mod;
};
for (auto p : centroids[u]) {
int cent, sub, d;
tie(cent, sub, d) = p;
if (d < seg[cent].size())
add(query(seg[cent][d], sub));
for (int i=0; i<seg[cent].size(); i+=SQ)
if (i > d)
add(query(seg[cent][i], sub));
}
return res;
}
int main() {
// read graph
cin >> n >> mod;
for (int i=0; i<n-1; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// centroid decomposition
centroidDecomposition(1);
// initial state
for (int i=1; i<=n; i++) cin >> h[i];
for (int i=1; i<=n; i++) updateVertex(i, 0, h[i]);
// answer queries
int q; cin >> q;
while (q--) {
int t; cin >> t;
if (t == 1) {
int x, d, w; cin >> x >> d >> w;
updateVertex(x, d, w);
}
if (t == 2) {
int x; cin >> x;
cout << queryVertex(x) << endl;
}
}
}
Compilation message
sprinkler.cpp: In function 'int queryVertex(int)':
sprinkler.cpp:114:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | if (d < seg[cent].size())
| ~~^~~~~~~~~~~~~~~~~~
sprinkler.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for (int i=0; i<seg[cent].size(); i+=SQ)
| ~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14292 KB |
Output is correct |
2 |
Correct |
8 ms |
14292 KB |
Output is correct |
3 |
Correct |
7 ms |
14292 KB |
Output is correct |
4 |
Correct |
12 ms |
14932 KB |
Output is correct |
5 |
Correct |
11 ms |
14788 KB |
Output is correct |
6 |
Correct |
15 ms |
14632 KB |
Output is correct |
7 |
Correct |
14 ms |
14900 KB |
Output is correct |
8 |
Correct |
10 ms |
14480 KB |
Output is correct |
9 |
Correct |
10 ms |
14292 KB |
Output is correct |
10 |
Correct |
8 ms |
14412 KB |
Output is correct |
11 |
Correct |
8 ms |
14292 KB |
Output is correct |
12 |
Correct |
8 ms |
14420 KB |
Output is correct |
13 |
Correct |
8 ms |
14292 KB |
Output is correct |
14 |
Correct |
8 ms |
14292 KB |
Output is correct |
15 |
Correct |
9 ms |
14292 KB |
Output is correct |
16 |
Correct |
8 ms |
14292 KB |
Output is correct |
17 |
Correct |
9 ms |
14292 KB |
Output is correct |
18 |
Correct |
10 ms |
14292 KB |
Output is correct |
19 |
Correct |
8 ms |
14292 KB |
Output is correct |
20 |
Correct |
8 ms |
14292 KB |
Output is correct |
21 |
Correct |
9 ms |
14292 KB |
Output is correct |
22 |
Correct |
8 ms |
14292 KB |
Output is correct |
23 |
Correct |
9 ms |
14292 KB |
Output is correct |
24 |
Correct |
8 ms |
14292 KB |
Output is correct |
25 |
Correct |
8 ms |
14292 KB |
Output is correct |
26 |
Correct |
10 ms |
14292 KB |
Output is correct |
27 |
Correct |
8 ms |
14292 KB |
Output is correct |
28 |
Correct |
9 ms |
14292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14292 KB |
Output is correct |
2 |
Correct |
2368 ms |
107644 KB |
Output is correct |
3 |
Correct |
1783 ms |
104320 KB |
Output is correct |
4 |
Correct |
2366 ms |
163552 KB |
Output is correct |
5 |
Correct |
1980 ms |
105848 KB |
Output is correct |
6 |
Correct |
1742 ms |
95392 KB |
Output is correct |
7 |
Correct |
1604 ms |
85636 KB |
Output is correct |
8 |
Correct |
1126 ms |
49308 KB |
Output is correct |
9 |
Correct |
2583 ms |
166376 KB |
Output is correct |
10 |
Correct |
2087 ms |
162260 KB |
Output is correct |
11 |
Correct |
2233 ms |
107512 KB |
Output is correct |
12 |
Correct |
1762 ms |
104464 KB |
Output is correct |
13 |
Correct |
943 ms |
55376 KB |
Output is correct |
14 |
Correct |
1074 ms |
59736 KB |
Output is correct |
15 |
Correct |
1112 ms |
63436 KB |
Output is correct |
16 |
Correct |
1116 ms |
66616 KB |
Output is correct |
17 |
Correct |
1231 ms |
69584 KB |
Output is correct |
18 |
Correct |
9 ms |
14292 KB |
Output is correct |
19 |
Correct |
8 ms |
14292 KB |
Output is correct |
20 |
Correct |
9 ms |
14292 KB |
Output is correct |
21 |
Correct |
8 ms |
14292 KB |
Output is correct |
22 |
Correct |
8 ms |
14292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14292 KB |
Output is correct |
2 |
Correct |
2368 ms |
107644 KB |
Output is correct |
3 |
Correct |
1783 ms |
104320 KB |
Output is correct |
4 |
Correct |
2366 ms |
163552 KB |
Output is correct |
5 |
Correct |
1980 ms |
105848 KB |
Output is correct |
6 |
Correct |
1742 ms |
95392 KB |
Output is correct |
7 |
Correct |
1604 ms |
85636 KB |
Output is correct |
8 |
Correct |
1126 ms |
49308 KB |
Output is correct |
9 |
Correct |
2583 ms |
166376 KB |
Output is correct |
10 |
Correct |
2087 ms |
162260 KB |
Output is correct |
11 |
Correct |
2233 ms |
107512 KB |
Output is correct |
12 |
Correct |
1762 ms |
104464 KB |
Output is correct |
13 |
Correct |
943 ms |
55376 KB |
Output is correct |
14 |
Correct |
1074 ms |
59736 KB |
Output is correct |
15 |
Correct |
1112 ms |
63436 KB |
Output is correct |
16 |
Correct |
1116 ms |
66616 KB |
Output is correct |
17 |
Correct |
1231 ms |
69584 KB |
Output is correct |
18 |
Correct |
9 ms |
14292 KB |
Output is correct |
19 |
Correct |
8 ms |
14292 KB |
Output is correct |
20 |
Correct |
9 ms |
14292 KB |
Output is correct |
21 |
Correct |
8 ms |
14292 KB |
Output is correct |
22 |
Correct |
8 ms |
14292 KB |
Output is correct |
23 |
Correct |
7 ms |
14292 KB |
Output is correct |
24 |
Correct |
2254 ms |
107640 KB |
Output is correct |
25 |
Correct |
1769 ms |
104264 KB |
Output is correct |
26 |
Correct |
2357 ms |
164288 KB |
Output is correct |
27 |
Correct |
2041 ms |
105856 KB |
Output is correct |
28 |
Correct |
1811 ms |
95292 KB |
Output is correct |
29 |
Correct |
1569 ms |
85544 KB |
Output is correct |
30 |
Correct |
1140 ms |
49392 KB |
Output is correct |
31 |
Correct |
2550 ms |
165152 KB |
Output is correct |
32 |
Correct |
2050 ms |
162496 KB |
Output is correct |
33 |
Correct |
2198 ms |
107576 KB |
Output is correct |
34 |
Correct |
1727 ms |
104396 KB |
Output is correct |
35 |
Correct |
8 ms |
14420 KB |
Output is correct |
36 |
Correct |
8 ms |
14292 KB |
Output is correct |
37 |
Correct |
8 ms |
14360 KB |
Output is correct |
38 |
Correct |
8 ms |
14420 KB |
Output is correct |
39 |
Correct |
8 ms |
14420 KB |
Output is correct |
40 |
Correct |
8 ms |
14292 KB |
Output is correct |
41 |
Correct |
9 ms |
14332 KB |
Output is correct |
42 |
Correct |
9 ms |
14320 KB |
Output is correct |
43 |
Correct |
8 ms |
14292 KB |
Output is correct |
44 |
Correct |
8 ms |
14404 KB |
Output is correct |
45 |
Correct |
8 ms |
14420 KB |
Output is correct |
46 |
Correct |
9 ms |
14292 KB |
Output is correct |
47 |
Correct |
10 ms |
14292 KB |
Output is correct |
48 |
Correct |
9 ms |
14292 KB |
Output is correct |
49 |
Correct |
8 ms |
14292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14292 KB |
Output is correct |
2 |
Correct |
2633 ms |
163604 KB |
Output is correct |
3 |
Correct |
2514 ms |
162028 KB |
Output is correct |
4 |
Correct |
2500 ms |
162200 KB |
Output is correct |
5 |
Correct |
2157 ms |
104380 KB |
Output is correct |
6 |
Correct |
1949 ms |
91864 KB |
Output is correct |
7 |
Correct |
1819 ms |
83236 KB |
Output is correct |
8 |
Correct |
1198 ms |
47708 KB |
Output is correct |
9 |
Correct |
2593 ms |
162552 KB |
Output is correct |
10 |
Correct |
2522 ms |
161660 KB |
Output is correct |
11 |
Correct |
2273 ms |
104868 KB |
Output is correct |
12 |
Correct |
2130 ms |
104452 KB |
Output is correct |
13 |
Correct |
2249 ms |
84024 KB |
Output is correct |
14 |
Correct |
2272 ms |
85796 KB |
Output is correct |
15 |
Correct |
8 ms |
14292 KB |
Output is correct |
16 |
Correct |
8 ms |
14300 KB |
Output is correct |
17 |
Correct |
9 ms |
14332 KB |
Output is correct |
18 |
Correct |
9 ms |
14292 KB |
Output is correct |
19 |
Correct |
8 ms |
14292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
14400 KB |
Output is correct |
2 |
Correct |
2656 ms |
165184 KB |
Output is correct |
3 |
Correct |
2729 ms |
161996 KB |
Output is correct |
4 |
Correct |
2914 ms |
163404 KB |
Output is correct |
5 |
Correct |
2443 ms |
105924 KB |
Output is correct |
6 |
Correct |
2048 ms |
94848 KB |
Output is correct |
7 |
Correct |
1846 ms |
86332 KB |
Output is correct |
8 |
Correct |
1230 ms |
49156 KB |
Output is correct |
9 |
Correct |
2783 ms |
165452 KB |
Output is correct |
10 |
Correct |
2684 ms |
162632 KB |
Output is correct |
11 |
Correct |
2451 ms |
107336 KB |
Output is correct |
12 |
Correct |
2296 ms |
104492 KB |
Output is correct |
13 |
Correct |
2283 ms |
84428 KB |
Output is correct |
14 |
Correct |
2383 ms |
85892 KB |
Output is correct |
15 |
Correct |
10 ms |
14408 KB |
Output is correct |
16 |
Correct |
9 ms |
14420 KB |
Output is correct |
17 |
Correct |
9 ms |
14292 KB |
Output is correct |
18 |
Correct |
9 ms |
14292 KB |
Output is correct |
19 |
Correct |
9 ms |
14292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14292 KB |
Output is correct |
2 |
Correct |
8 ms |
14292 KB |
Output is correct |
3 |
Correct |
7 ms |
14292 KB |
Output is correct |
4 |
Correct |
12 ms |
14932 KB |
Output is correct |
5 |
Correct |
11 ms |
14788 KB |
Output is correct |
6 |
Correct |
15 ms |
14632 KB |
Output is correct |
7 |
Correct |
14 ms |
14900 KB |
Output is correct |
8 |
Correct |
10 ms |
14480 KB |
Output is correct |
9 |
Correct |
10 ms |
14292 KB |
Output is correct |
10 |
Correct |
8 ms |
14412 KB |
Output is correct |
11 |
Correct |
8 ms |
14292 KB |
Output is correct |
12 |
Correct |
8 ms |
14420 KB |
Output is correct |
13 |
Correct |
8 ms |
14292 KB |
Output is correct |
14 |
Correct |
8 ms |
14292 KB |
Output is correct |
15 |
Correct |
9 ms |
14292 KB |
Output is correct |
16 |
Correct |
8 ms |
14292 KB |
Output is correct |
17 |
Correct |
9 ms |
14292 KB |
Output is correct |
18 |
Correct |
10 ms |
14292 KB |
Output is correct |
19 |
Correct |
8 ms |
14292 KB |
Output is correct |
20 |
Correct |
8 ms |
14292 KB |
Output is correct |
21 |
Correct |
9 ms |
14292 KB |
Output is correct |
22 |
Correct |
8 ms |
14292 KB |
Output is correct |
23 |
Correct |
9 ms |
14292 KB |
Output is correct |
24 |
Correct |
8 ms |
14292 KB |
Output is correct |
25 |
Correct |
8 ms |
14292 KB |
Output is correct |
26 |
Correct |
10 ms |
14292 KB |
Output is correct |
27 |
Correct |
8 ms |
14292 KB |
Output is correct |
28 |
Correct |
9 ms |
14292 KB |
Output is correct |
29 |
Correct |
8 ms |
14292 KB |
Output is correct |
30 |
Correct |
2368 ms |
107644 KB |
Output is correct |
31 |
Correct |
1783 ms |
104320 KB |
Output is correct |
32 |
Correct |
2366 ms |
163552 KB |
Output is correct |
33 |
Correct |
1980 ms |
105848 KB |
Output is correct |
34 |
Correct |
1742 ms |
95392 KB |
Output is correct |
35 |
Correct |
1604 ms |
85636 KB |
Output is correct |
36 |
Correct |
1126 ms |
49308 KB |
Output is correct |
37 |
Correct |
2583 ms |
166376 KB |
Output is correct |
38 |
Correct |
2087 ms |
162260 KB |
Output is correct |
39 |
Correct |
2233 ms |
107512 KB |
Output is correct |
40 |
Correct |
1762 ms |
104464 KB |
Output is correct |
41 |
Correct |
943 ms |
55376 KB |
Output is correct |
42 |
Correct |
1074 ms |
59736 KB |
Output is correct |
43 |
Correct |
1112 ms |
63436 KB |
Output is correct |
44 |
Correct |
1116 ms |
66616 KB |
Output is correct |
45 |
Correct |
1231 ms |
69584 KB |
Output is correct |
46 |
Correct |
9 ms |
14292 KB |
Output is correct |
47 |
Correct |
8 ms |
14292 KB |
Output is correct |
48 |
Correct |
9 ms |
14292 KB |
Output is correct |
49 |
Correct |
8 ms |
14292 KB |
Output is correct |
50 |
Correct |
8 ms |
14292 KB |
Output is correct |
51 |
Correct |
7 ms |
14292 KB |
Output is correct |
52 |
Correct |
2254 ms |
107640 KB |
Output is correct |
53 |
Correct |
1769 ms |
104264 KB |
Output is correct |
54 |
Correct |
2357 ms |
164288 KB |
Output is correct |
55 |
Correct |
2041 ms |
105856 KB |
Output is correct |
56 |
Correct |
1811 ms |
95292 KB |
Output is correct |
57 |
Correct |
1569 ms |
85544 KB |
Output is correct |
58 |
Correct |
1140 ms |
49392 KB |
Output is correct |
59 |
Correct |
2550 ms |
165152 KB |
Output is correct |
60 |
Correct |
2050 ms |
162496 KB |
Output is correct |
61 |
Correct |
2198 ms |
107576 KB |
Output is correct |
62 |
Correct |
1727 ms |
104396 KB |
Output is correct |
63 |
Correct |
8 ms |
14420 KB |
Output is correct |
64 |
Correct |
8 ms |
14292 KB |
Output is correct |
65 |
Correct |
8 ms |
14360 KB |
Output is correct |
66 |
Correct |
8 ms |
14420 KB |
Output is correct |
67 |
Correct |
8 ms |
14420 KB |
Output is correct |
68 |
Correct |
8 ms |
14292 KB |
Output is correct |
69 |
Correct |
9 ms |
14332 KB |
Output is correct |
70 |
Correct |
9 ms |
14320 KB |
Output is correct |
71 |
Correct |
8 ms |
14292 KB |
Output is correct |
72 |
Correct |
8 ms |
14404 KB |
Output is correct |
73 |
Correct |
8 ms |
14420 KB |
Output is correct |
74 |
Correct |
9 ms |
14292 KB |
Output is correct |
75 |
Correct |
10 ms |
14292 KB |
Output is correct |
76 |
Correct |
9 ms |
14292 KB |
Output is correct |
77 |
Correct |
8 ms |
14292 KB |
Output is correct |
78 |
Correct |
7 ms |
14292 KB |
Output is correct |
79 |
Correct |
2633 ms |
163604 KB |
Output is correct |
80 |
Correct |
2514 ms |
162028 KB |
Output is correct |
81 |
Correct |
2500 ms |
162200 KB |
Output is correct |
82 |
Correct |
2157 ms |
104380 KB |
Output is correct |
83 |
Correct |
1949 ms |
91864 KB |
Output is correct |
84 |
Correct |
1819 ms |
83236 KB |
Output is correct |
85 |
Correct |
1198 ms |
47708 KB |
Output is correct |
86 |
Correct |
2593 ms |
162552 KB |
Output is correct |
87 |
Correct |
2522 ms |
161660 KB |
Output is correct |
88 |
Correct |
2273 ms |
104868 KB |
Output is correct |
89 |
Correct |
2130 ms |
104452 KB |
Output is correct |
90 |
Correct |
2249 ms |
84024 KB |
Output is correct |
91 |
Correct |
2272 ms |
85796 KB |
Output is correct |
92 |
Correct |
8 ms |
14292 KB |
Output is correct |
93 |
Correct |
8 ms |
14300 KB |
Output is correct |
94 |
Correct |
9 ms |
14332 KB |
Output is correct |
95 |
Correct |
9 ms |
14292 KB |
Output is correct |
96 |
Correct |
8 ms |
14292 KB |
Output is correct |
97 |
Correct |
9 ms |
14400 KB |
Output is correct |
98 |
Correct |
2656 ms |
165184 KB |
Output is correct |
99 |
Correct |
2729 ms |
161996 KB |
Output is correct |
100 |
Correct |
2914 ms |
163404 KB |
Output is correct |
101 |
Correct |
2443 ms |
105924 KB |
Output is correct |
102 |
Correct |
2048 ms |
94848 KB |
Output is correct |
103 |
Correct |
1846 ms |
86332 KB |
Output is correct |
104 |
Correct |
1230 ms |
49156 KB |
Output is correct |
105 |
Correct |
2783 ms |
165452 KB |
Output is correct |
106 |
Correct |
2684 ms |
162632 KB |
Output is correct |
107 |
Correct |
2451 ms |
107336 KB |
Output is correct |
108 |
Correct |
2296 ms |
104492 KB |
Output is correct |
109 |
Correct |
2283 ms |
84428 KB |
Output is correct |
110 |
Correct |
2383 ms |
85892 KB |
Output is correct |
111 |
Correct |
10 ms |
14408 KB |
Output is correct |
112 |
Correct |
9 ms |
14420 KB |
Output is correct |
113 |
Correct |
9 ms |
14292 KB |
Output is correct |
114 |
Correct |
9 ms |
14292 KB |
Output is correct |
115 |
Correct |
9 ms |
14292 KB |
Output is correct |
116 |
Correct |
2368 ms |
105492 KB |
Output is correct |
117 |
Correct |
2321 ms |
104236 KB |
Output is correct |
118 |
Correct |
2616 ms |
164080 KB |
Output is correct |
119 |
Correct |
2260 ms |
105936 KB |
Output is correct |
120 |
Correct |
2025 ms |
92700 KB |
Output is correct |
121 |
Correct |
2025 ms |
87516 KB |
Output is correct |
122 |
Correct |
1306 ms |
49272 KB |
Output is correct |
123 |
Correct |
2736 ms |
165292 KB |
Output is correct |
124 |
Correct |
2649 ms |
162228 KB |
Output is correct |
125 |
Correct |
2347 ms |
107040 KB |
Output is correct |
126 |
Correct |
2316 ms |
104672 KB |
Output is correct |
127 |
Correct |
2376 ms |
104332 KB |
Output is correct |
128 |
Correct |
2532 ms |
84420 KB |
Output is correct |
129 |
Correct |
2612 ms |
85608 KB |
Output is correct |