#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, DIFF = 1;
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]);
}
}
vector<int> g[N];
int h[N], sz[N];
char used[N];
struct CentroidNode {
int parent, depth, sz;
vector<int> ob, pb;
int *op[DIFF], *pp[DIFF];
ll *oi, *pi;
} tc[N];
const int INT_MEM = 136806840, LL_MEM = 15200760;
int int_mem[INT_MEM];
ll ll_mem[LL_MEM];
int next_free = 0, ll_free = 0;
int *allocate(int x) {
int *res = int_mem + next_free;
next_free += x;
assert(next_free < INT_MEM);
return res;
}
ll *allocatell(int x) {
ll *res = ll_mem + ll_free;
ll_free += x;
assert(ll_free < LL_MEM);
return res;
}
int where[LOG][N], where2[LOG][N];
int dfs_sz(int u, int p = -1) {
if (used[u]) {
return 0;
}
sz[u] = 1;
for (int v : g[u]) {
if (v == p) {
continue;
}
sz[u] += dfs_sz(v, u);
}
return sz[u];
}
int dfs_find_centroid(int u, int csz, int p = -1) {
for (int v : g[u]) {
if (v != p && !used[v] && 2 * sz[v] >= csz) {
return dfs_find_centroid(v, csz, u);
}
}
return u;
}
int croot;
queue<tuple<int, int, int>> bfs;
void dfs_centroid(int root, int parent = -1, int depth = 0) {
int centroid = dfs_find_centroid(root, dfs_sz(root));
auto &node = tc[centroid];
node.parent = parent;
node.depth = depth;
node.sz = sz[root];
if (parent == -1) {
croot = centroid;
}
bfs.push({1, root, -1});
int prev = -1, at = 0;
node.pb.push_back(0);
while (sz(bfs)) {
auto [d, u, p] = bfs.front();
bfs.pop();
where2[depth][u] = at;
if (prev != d) {
node.pb.push_back(at);
prev = d;
}
++at;
for (int v : g[u]) {
if (!used[v] && v != p) {
bfs.push({d + 1, v, u});
}
}
}
bfs.push({0, centroid, -1});
prev = -1, at = 0;
while (sz(bfs)) {
auto [d, u, p] = bfs.front();
bfs.pop();
where[depth][u] = at;
if (prev != d) {
node.ob.push_back(at);
prev = d;
}
++at;
for (int v : g[u]) {
if (!used[v] && v != p) {
bfs.push({d + 1, v, u});
}
}
}
for (int i = 0; i < DIFF; ++i) {
node.op[i] = allocate(2 * node.sz);
node.pp[i] = allocate(2 * node.sz);
}
node.oi = allocatell(2 * node.sz);
node.pi = allocatell(2 * node.sz);
used[centroid] = 1;
for (int v : g[centroid]) {
if (!used[v]) {
dfs_centroid(v, centroid, depth + 1);
}
}
}
int ipow[EULER], depth[N];
pair<int, int> sp[LOG][EULER];
int order[N], timer = 0;
void dfs_euler(int u, int d = 0, int p = -1) {
order[u] = timer;
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<pair<int, int>> factor(int x) {
vector<pair<int, int>> res;
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
res.push_back({i, 0});
while (x % i == 0) {
++res.back().y;
x /= i;
}
}
}
if (x != 1) {
res.push_back({x, 1});
}
return res;
}
pair<vector<int>, int> get_pw(int x, const vector<pair<int, int>> &fact) {
vector<int> pw;
for (auto [prime, _] : fact) {
pw.push_back(0);
while (x % prime == 0) {
x /= prime;
++pw.back();
}
}
return {pw, x};
}
void exgcd(int a, int b, ll &x, ll &y) {
if (b == 0) {
x = 1;
y = 0;
return;
}
exgcd(b, a % b, x, y);
ll nw = x - (a / b) * y;
x = y;
y = nw;
}
int diff;
ll l;
template <typename T>
void tdo(int l, int r, int s, T func) {
l += s;
r += s;
while (l <= r) {
if (l & 1) func(l);
if (!(r & 1)) func(r);
l = (l + 1) / 2;
r = (r - 1) / 2;
}
}
void apply_for(const vector<int> &part, int ineq, int inv, int u, int x, int d) {
auto &node = tc[u];
int dst = d - dist(u, x);
int bound = dst < 0 ? 0 : (dst + 1 >= sz(node.ob) ? node.sz : node.ob[dst + 1]);
for (int i = 0; i < diff; ++i) {
if (part[i] == 0) {
continue;
}
tdo(0, bound - 1, node.sz, [&](int j) {
node.op[i][j] += part[i];
});
}
if (ineq != 1) {
tdo(0, bound - 1, node.sz, [&](int j) {
(node.oi[j] *= ineq) %= l;
});
}
if (node.parent == -1) {
return;
}
dst = d - dist(node.parent, x);
bound = dst < 0 ? 0 : (dst + 1 >= sz(node.pb) ? node.sz : node.pb[dst + 1]);
for (int i = 0; i < diff; ++i) {
if (part[i] == 0) {
continue;
}
// for (int j = 0; j < bound; ++j) {
// node.pp[i][j] -= part[i];
// }
tdo(0, bound - 1, node.sz, [&](int j) {
node.pp[i][j] -= part[i];
});
}
if (inv != 1) {
// for (int j = 0; j < bound; ++j) {
// (node.pi[j] *= inv) %= l;
// }
tdo(0, bound - 1, node.sz, [&](int j) {
(node.pi[j] *= inv) %= l;
});
}
}
void count_for(vector<int> &part, ll &ineq, int u, int x) {
const auto &node = tc[u];
int i = where[node.depth][x] + node.sz;
while (i) {
for (int j = 0; j < diff; ++j) {
part[j] += node.op[j][i];
}
(ineq *= node.oi[i]) %= l;
i /= 2;
}
if (node.parent == -1) {
return;
}
int st = where2[node.depth][x] + node.sz;
for (int j = 0; j < diff; ++j) {
i = st;
while (i) {
part[j] += node.pp[j][i];
i /= 2;
}
}
i = st;
while (i) {
(ineq *= node.pi[i]) %= l;
i /= 2;
}
}
ll fpow(ll a, ll b) {
ll c = 1;
for (int i = 1; i <= b; i *= 2) {
if (b & i) {
(c *= a) %= l;
}
(a *= a) %= l;
}
return c;
}
signed main() {
#ifdef DEBUG
freopen("output.txt", "w", stdout);
#endif
int n = read_int();
l = read_int();
fill(all(ll_mem), 1);
for (int i = 1; i < n; ++i) {
int u = read_int(), v = read_int();
g[--u].push_back(--v);
g[v].push_back(u);
}
for (int i = 0; i < n; ++i) {
h[i] = read_int();
}
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;
}
dfs_centroid(0);
int queries = read_int();
auto fact = factor(int(l));
diff = sz(fact);
diff = 1;
fact = {{l, 1}};
while (queries--) {
int type = read_int();
if (type == 1) {
int x = read_int(), d = read_int(), w = read_int();
--x;
if (!w) {
w = int(l);
}
auto [part, ineq] = get_pw(w, fact);
ll inv, tmp;
exgcd(ineq, int(l), inv, tmp);
inv = (inv % l + l) % l;
int curr = x;
while (curr != -1) {
apply_for(part, ineq, int(inv), curr, x, d);
curr = tc[curr].parent;
}
} else {
int x = read_int() - 1;
vector<int> part(diff);
ll ineq = 1;
int curr = x;
while (curr != -1) {
count_for(part, ineq, curr, x);
curr = tc[curr].parent;
}
ll res = 1;
for (int i = 0; i < diff; ++i) {
(res *= fpow(fact[i].x, part[i])) %= l;
}
(res *= ineq) %= l;
write_int((h[x] * res) % l);
write_char('\n');
// for (int u : part) {
// cout << u << " ";
// }
// cout << ineq << "\n";
}
}
wflush();
cerr << clock() << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
142828 KB |
Output is correct |
| 2 |
Correct |
70 ms |
142812 KB |
Output is correct |
| 3 |
Correct |
69 ms |
142796 KB |
Output is correct |
| 4 |
Incorrect |
90 ms |
143436 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
142852 KB |
Output is correct |
| 2 |
Correct |
3821 ms |
254356 KB |
Output is correct |
| 3 |
Correct |
2379 ms |
250624 KB |
Output is correct |
| 4 |
Execution timed out |
4089 ms |
282780 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
142852 KB |
Output is correct |
| 2 |
Correct |
3821 ms |
254356 KB |
Output is correct |
| 3 |
Correct |
2379 ms |
250624 KB |
Output is correct |
| 4 |
Execution timed out |
4089 ms |
282780 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
142816 KB |
Output is correct |
| 2 |
Execution timed out |
4058 ms |
320748 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
142852 KB |
Output is correct |
| 2 |
Execution timed out |
4080 ms |
283172 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
142828 KB |
Output is correct |
| 2 |
Correct |
70 ms |
142812 KB |
Output is correct |
| 3 |
Correct |
69 ms |
142796 KB |
Output is correct |
| 4 |
Incorrect |
90 ms |
143436 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
