#include <bits/stdc++.h>
#include <random>
#ifndef LOCAL
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
typedef long long ll;
typedef double dd;
typedef long double ld;
typedef unsigned int uii;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void solve();
mt19937_64 mt(1);
int32_t main() {
#ifdef LOCAL
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#else
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
//freopen("amusing.in", "r", stdin);
//freopen("amusing.out", "w", stdout);
#endif
cout << fixed << setprecision(30);
int tests = 1;
//cin >> tests;
while (tests--) {
solve();
}
}
#define int ll
ll mod;
class SegmentTree {
public:
void build(const vector<int>& b) {
int sz = 1;
while (sz < b.size()) {
sz *= 2;
}
x.resize(2 * sz - 1);
vn.resize(2 * sz - 1, 1);
size = 2 * sz - 1;
for (int i = sz - 1; i < 2 * sz - 1; i++) {
if (i - sz + 1 < b.size()) {
x[i] = b[i - sz + 1];
} else {
x[i] = 0;
}
}
for (int i = sz - 2; i >= 0; i--) {
//update(i);
x[i] = 0;
}
}
int get(int l, int r, int i = 0, int lx = 0, int rx = -1) {
if (rx == -1) {
rx = size / 2;
}
if (lx > r || rx < l) {
return 0;
}
if (lx >= l && rx <= r) {
return x[i];
}
updateVN(i);
return get(l, r, 2 * i + 1, lx, (rx + lx) / 2) + get(l, r, 2 * i + 2, (rx + lx) / 2 + 1, rx);
}
void change(int ind, int c, int i = 0, int lx = 0, int rx = -1) {
if (rx == -1) {
rx = size / 2;
}
if (lx == rx) {
x[i] = c;
return;
}
updateVN(i);
if ((rx + lx) / 2 >= ind) {
change(ind, c, 2 * i + 1, lx, (rx + lx) / 2);
} else {
change(ind, c, 2 * i + 2, (rx + lx) / 2 + 1, rx);
}
//update(i);
}
void plusOtr(int l, int r, ll p, int i = 0, int lx = 0, int rx = -1) {
if (r < l) {
return;
}
if (rx == -1) {
rx = size / 2;
}
if (lx >= l && rx <= r) {
x[i] = (x[i] * p) % mod;
vn[i] = (vn[i] * p) % mod;
return;
}
if (lx > r || rx < l) {
return;
}
updateVN(i);
plusOtr(l, r, p, 2 * i + 1, lx, (rx + lx) / 2);
plusOtr(l, r, p, 2 * i + 2, (rx + lx) / 2 + 1, rx);
//update(i);
}
private:
vector<ll> x, vn;
int size;
void updateVN(int i) {
if (2 * i + 2 < size) {
if (vn[i] != 1) {
if (x[2 * i + 1]) {
x[2 * i + 1] = (x[2 * i + 1] * vn[i]) % mod;
}
vn[2 * i + 1] = (vn[2 * i + 1] * vn[i]) % mod;
if (x[2 * i + 2]) {
x[2 * i + 2] = (x[2 * i + 2] * vn[i]) % mod;
}
vn[2 * i + 2] = (vn[2 * i + 2] * vn[i]) % mod;
vn[i] = 1;
}
}
}
void update(int i) {
if (2 * i + 2 < size) {
x[i] = x[2 * i + 1] + x[2 * i + 2];
}
}
};
void dfs(int s, int p, vector<vector<int>>& g, vector<int>& dist, vector<vector<int>>& d, vector<vector<pair<int, int>>>& seg, vector<int>& pr) {
if (p != -1) {
dist[s] = dist[p] + 1;
} else {
dist[s] = 0;
}
pr[s] = p;
d[dist[s]].push_back(s);
seg[s][0] = {d[dist[s]].size() - 1, d[dist[s]].size() - 1};
vector<int> l(41, -100);
bool f = true;
for (int i : g[s]) {
if (i != p) {
dfs(i, s, g, dist, d, seg, pr);
if (f) {
f = false;
for (int j = 1; j < 41; j++) {
seg[s][j].x = seg[i][j - 1].x;
}
}
for (int j = 1; j < 41; j++) {
l[j] = seg[i][j - 1].y;
}
}
}
for (int j = 1; j < 41; j++) {
seg[s][j].y = l[j];
}
}
void solve() {
int n;
cin >> n >> mod;
vector<vector<int>> g(n), d(n);
vector<int> deg(n, 0), dist(n), h(n), p(n);
vector<vector<pair<int, int>>> seg(n, vector<pair<int, int>>(41, {0, -100}));
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v; u--; v--;
g[u].push_back(v);
g[v].push_back(u);
deg[u]++;
deg[v]++;
}
int root = 0;
for (int i = 0; i < n; i++) {
if (deg[i] == 1) {
root = i;
break;
}
}
dfs(root, -1, g, dist, d, seg, p);
for (int i = 0; i < n; i++) {
cin >> h[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < d[i].size(); j++) {
d[i][j] = h[d[i][j]];
}
}
vector<SegmentTree> dec(n);
for (int i = 0; i < n; i++) {
dec[i].build(d[i]);
}
int q;
cin >> q;
while (q--) {
int t;
cin >> t;
if (t == 1) {
int x, dk, wk;
cin >> x >> dk >> wk; x--;
for (int l = -dk; l <= dk; l++) {
if (dist[x] - l < 0) {
break;
}
if (dist[x] - l >= n) {
continue;
}
int l1 = INT32_MAX, r1 = INT32_MIN, nw = x;
for (int i = 0; i <= dk && nw >= 0 && 2 * i - l <= dk; i++) {
if (i - l < 0) {
nw = p[nw];
continue;
}
l1 = min(l1, seg[nw][i - l].x);
r1 = max(r1, seg[nw][i - l].y);
nw = p[nw];
}
dec[dist[x] - l].plusOtr(l1, r1, wk);
}
} else {
int x;
cin >> x; x--;
cout << (dec[dist[x]].get(seg[x][0].x, seg[x][0].y) % mod + mod) % mod << '\n';
}
}
}
Compilation message
sprinkler.cpp: In member function 'void SegmentTree::build(const std::vector<long long int>&)':
sprinkler.cpp:52:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | while (sz < b.size()) {
| ~~~^~~~~~~~~~
sprinkler.cpp:59:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | if (i - sz + 1 < b.size()) {
| ~~~~~~~~~~~^~~~~~~~~~
sprinkler.cpp: In function 'void solve()':
sprinkler.cpp:204:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
204 | for (int j = 0; j < d[i].size(); j++) {
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
3 ms |
1624 KB |
Output is correct |
5 |
Incorrect |
3 ms |
1372 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
593 ms |
197760 KB |
Output is correct |
3 |
Correct |
789 ms |
195044 KB |
Output is correct |
4 |
Correct |
654 ms |
274684 KB |
Output is correct |
5 |
Correct |
601 ms |
196208 KB |
Output is correct |
6 |
Correct |
597 ms |
196300 KB |
Output is correct |
7 |
Correct |
647 ms |
195760 KB |
Output is correct |
8 |
Correct |
515 ms |
195236 KB |
Output is correct |
9 |
Correct |
611 ms |
276272 KB |
Output is correct |
10 |
Correct |
684 ms |
273228 KB |
Output is correct |
11 |
Correct |
517 ms |
197804 KB |
Output is correct |
12 |
Correct |
721 ms |
195008 KB |
Output is correct |
13 |
Correct |
445 ms |
194764 KB |
Output is correct |
14 |
Correct |
557 ms |
196048 KB |
Output is correct |
15 |
Correct |
590 ms |
194980 KB |
Output is correct |
16 |
Correct |
583 ms |
195248 KB |
Output is correct |
17 |
Correct |
629 ms |
194756 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
593 ms |
197760 KB |
Output is correct |
3 |
Correct |
789 ms |
195044 KB |
Output is correct |
4 |
Correct |
654 ms |
274684 KB |
Output is correct |
5 |
Correct |
601 ms |
196208 KB |
Output is correct |
6 |
Correct |
597 ms |
196300 KB |
Output is correct |
7 |
Correct |
647 ms |
195760 KB |
Output is correct |
8 |
Correct |
515 ms |
195236 KB |
Output is correct |
9 |
Correct |
611 ms |
276272 KB |
Output is correct |
10 |
Correct |
684 ms |
273228 KB |
Output is correct |
11 |
Correct |
517 ms |
197804 KB |
Output is correct |
12 |
Correct |
721 ms |
195008 KB |
Output is correct |
13 |
Correct |
445 ms |
194764 KB |
Output is correct |
14 |
Correct |
557 ms |
196048 KB |
Output is correct |
15 |
Correct |
590 ms |
194980 KB |
Output is correct |
16 |
Correct |
583 ms |
195248 KB |
Output is correct |
17 |
Correct |
629 ms |
194756 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Incorrect |
565 ms |
197744 KB |
Output isn't correct |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1176 ms |
273736 KB |
Output is correct |
3 |
Execution timed out |
4057 ms |
273132 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1263 ms |
276388 KB |
Output is correct |
3 |
Execution timed out |
4042 ms |
273180 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
3 ms |
1624 KB |
Output is correct |
5 |
Incorrect |
3 ms |
1372 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |