//I wrote this code 4 u <3
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
template <class Info, class Merge = plus<Info>>
class SPT { //0-indexed, [l, r]
public:
int n;
vector<vector<Info>> mat;
const Merge merge;
SPT(vector<Info> a, const Info x = Info()) : merge(Merge()) {
n = static_cast<int>(a.size());
int max_log = 32 - __builtin_clz(n);
mat.resize(max_log);
mat[0] = a;
for (int j = 1; j < max_log; j++) {
mat[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); i++) {
mat[j][i] = merge(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
}
}
}
Info get(int from, int to) const {
assert(0 <= from && from <= to && to <= n - 1);
int lg = 32 - __builtin_clz(to - from + 1) - 1;
return merge(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
}
};
struct Info {
int u, d;
Info() = default;
Info(int _u, int _d) : u(_u), d(_d) {}
};
Info operator+(const Info &a, const Info &b) {
Info ret;
if (a.d < b.d) ret = a;
else ret = b;
return ret;
}
const int K = 777;
signed main(int32_t argc, char *argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, L;
cin >> n >> L;
vector<vector<int>> g(n);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<Info> ord;
vector<int> tin(n), dep(n);
auto Dfs = [&](auto&& self, int u, int p) -> void {
tin[u] = (int) ord.size();
ord.push_back({u, dep[u]});
for (auto to : g[u]) {
if (to == p) continue;
dep[to] = dep[u] + 1;
self(self, to, u);
ord.push_back({u, dep[u]});
}
};
dep[0] = 0;
Dfs(Dfs, 0, -1);
SPT kek(ord);
auto lca = [&](int u, int v) {
u = tin[u], v = tin[v];
if (u > v) swap(u, v);
return kek.get(u, v).u;
};
vector<int> a(n);
for (auto& x : a) cin >> x;
int q;
cin >> q;
for (int i = 0; i < q; i += K) {
vector<array<int, 3>> lazy;
for (int j = 0; j < min(q - i, K); ++j) {
int t, u;
cin >> t >> u;
--u;
if (t == 1) {
int d, w;
cin >> d >> w;
lazy.push_back({u, d, w});
} else {
int cur = a[u];
for (auto [x, y, w] : lazy) {
int dst = dep[u] + dep[x] - 2 * dep[lca(u, x)];
if (dst <= y) cur = (1ll * cur * w) % L;
}
cout << cur << '\n';
}
}
for (auto& [x, y, w] : lazy) {
queue<array<int, 3>> que;
que.push({x, -1, 0});
while (!que.empty()) {
auto [u, p, d] = que.front(); que.pop();
a[u] = (1ll * a[u] * w) % L;
if (d == y) continue;
for (auto to : g[u]) {
if (to == p) continue;
que.push({to, u, d + 1});
}
}
}
}
}
/*
*/
Compilation message
sprinkler.cpp: In function 'int main(int32_t, char**)':
sprinkler.cpp:84:9: error: missing template arguments before 'kek'
84 | SPT kek(ord);
| ^~~
sprinkler.cpp: In lambda function:
sprinkler.cpp:88:16: error: 'kek' was not declared in this scope
88 | return kek.get(u, v).u;
| ^~~
sprinkler.cpp: In function 'int main(int32_t, char**)':
sprinkler.cpp:106:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
106 | for (auto [x, y, w] : lazy) {
| ^
sprinkler.cpp:113:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
113 | for (auto& [x, y, w] : lazy) {
| ^
sprinkler.cpp:117:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
117 | auto [u, p, d] = que.front(); que.pop();
| ^
