//bs:sanitizers
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;
template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;
const int N = 2e5 + 10, EULER = 2 * N, LOG = 19;
const int BUFF = 4096;
char buff[BUFF + 1];
int buff_it = 0, buff_len = 0;
char wbuff[BUFF];
int wbuff_len = 0;
char read_char() {
if (buff_it == buff_len) {
buff_len = (int) fread(buff, 1, BUFF, stdin);
buff[buff_len] = 0;
buff_it = 0;
}
return buff[buff_it++];
}
int read_int() {
char c = ' ';
while (!isdigit(c = read_char()));
int res = 0;
do {
res *= 10;
res += c - '0';
} while (isdigit(c = read_char()));
return res;
}
void wflush() {
fwrite(wbuff, 1, wbuff_len, stdout);
wbuff_len = 0;
}
void write_char(char c) {
if (wbuff_len == BUFF) {
wflush();
}
wbuff[wbuff_len++] = c;
}
void write_int(ll x) {
static char cbuff[20];
int i = 0;
if (!x) {
write_char('0');
return;
}
for (; x; x /= 10) {
cbuff[i++] = char(x % 10 + '0');
}
for (; i--; ) {
write_char(cbuff[i]);
}
}
int n, modulo;
vector<int> g[N];
int ipow[EULER], depth[N];
pair<int, int> sp[LOG][EULER];
int order[N], timer = 0, parent[N];
void dfs_euler(int u, int d = 0, int p = -1) {
order[u] = timer;
parent[u] = p;
depth[u] = d;
sp[0][timer++] = {d, u};
for (int v : g[u]) {
if (v != p) {
dfs_euler(v, d + 1, u);
sp[0][timer++] = {d, u};
}
}
}
int lca(int u, int v) {
if (u == v) {
return u;
}
u = order[u];
v = order[v];
if (u > v) {
swap(u, v);
}
++v;
int pw = ipow[v - u];
return min(sp[pw][u], sp[pw][v - (1 << pw)]).y;
}
int dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
vector<int> layer[N];
pair<int, int> inv[N];
int layer_start[N];
int lnk[N];
ll t[2 * N];
int get(int u) {
auto [x, y] = inv[u];
return layer_start[x] + y;
}
void upd(int l, int r, int w) {
l += n;
r += n;
while (l <= r) {
if (l & 1) (t[l] *= w) %= modulo;
if (!(r & 1)) (t[r] *= w) %= modulo;
l = (l + 1) / 2;
r = (r - 1) / 2;
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
n = read_int(), modulo = read_int();
fill(t, t + 2 * n, 1);
for (int i = 1; i < n; ++i) {
int u, v;
u = read_int(), v = read_int();
g[--u].push_back(--v);
g[v].push_back(u);
}
dfs_euler(0);
for (int i = 1; i < LOG; ++i) {
for (int j = 0; j <= timer - (1 << i); ++j) {
sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
}
}
for (int i = 2; i <= timer; ++i) {
ipow[i] = ipow[i / 2] + 1;
}
queue<tuple<int, int, int>> bfs;
bfs.push({0, -1, 0});
layer[0].push_back(0);
while (sz(bfs)) {
auto [u, p, dst] = bfs.front();
bfs.pop();
lnk[u] = sz(layer[dst + 1]);
for (int v : g[u]) {
if (v != p) {
bfs.push({v, u, dst + 1});
inv[v] = {dst + 1, sz(layer[dst + 1])};
layer[dst + 1].push_back(v);
}
}
}
for (int i = 1; i < N; ++i) {
layer_start[i] = layer_start[i - 1] + sz(layer[i - 1]);
}
for (int i = 0; i < n; ++i) {
int x = read_int();
t[get(i) + n] = x;
}
int queries = read_int();
while (queries--) {
int type = read_int();
if (type == 1) {
int x = read_int(), d = read_int(), w = read_int();
--x;
auto upd_with_base = [&](int where, int index) {
int lef = max(index - d + abs(where - inv[x].x) - 1, -1), rig = index;
while (rig - lef > 1) {
int mid = (lef + rig) / 2;
if (dist(layer[where][mid], x) <= d) {
rig = mid;
} else {
lef = mid;
}
}
bool flag = (rig != index);
upd(layer_start[where] + rig, layer_start[where] + index - 1, w);
lef = index - 1, rig = min(sz(layer[where]), index + d - abs(where - inv[x].x) + 1);
while (rig - lef > 1) {
int mid = (lef + rig) / 2;
if (dist(layer[where][mid], x) <= d) {
lef = mid;
} else {
rig = mid;
}
}
flag |= index - 1 != lef;
upd(layer_start[where] + index, layer_start[where] + lef, w);
return flag;
};
for (int u = parent[x]; u != -1; u = parent[u]) {
if (!upd_with_base(inv[u].x, inv[u].y)) {
break;
}
}
int where = inv[x].x, index = inv[x].y;
while (1) {
// cout << where << " " << index << endl;
// cout << layer[where][index] << endl;
if (!upd_with_base(where, index)) {
break;
}
if (index == sz(layer[where])) {
++where;
index = sz(layer[where]);
} else {
index = lnk[layer[where][index]];
++where;
}
}
} else {
int x = read_int();
int i = get(x - 1) + n;
ll res = 1;
while (i) {
(res *= t[i]) %= modulo;
i /= 2;
}
write_int(res);
write_char('\n');
// cout << res << "\n";
}
// for (int j = 0; j < n; ++j) {
// int i = get(j) + n;
// ll res = 1;
// while (i) {
// (res *= t[i]) %= modulo;
// i /= 2;
// }
// cout << res << " ";
// }
// cout << endl;
}
wflush();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
10548 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
10472 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
10524 KB |
Output is correct |
| 2 |
Correct |
1108 ms |
103256 KB |
Output is correct |
| 3 |
Execution timed out |
4093 ms |
97488 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
10580 KB |
Output is correct |
| 2 |
Correct |
1108 ms |
99024 KB |
Output is correct |
| 3 |
Execution timed out |
4042 ms |
93432 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
10548 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
10472 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
