// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 400005;
const int MAXD = 41;
int n, l;
vii adj[MAXN];
int h[MAXN];
int q;
int m;
ii p[MAXN];
int pre[MAXN], pst[MAXN], ptr = 1;
void dfs(int u) {
REP (i, 0, adj[u].size()) {
if (adj[u][i].FI == p[u].FI) {
swap(adj[u][i], adj[u][SZ(adj[u]) - 1]);
break;
}
}
pre[u] = ptr;
for (auto &[v, id] : adj[u]) {
if (v == p[u].FI) continue;
id = ptr++;
p[v] = {u, id};
}
while (__builtin_popcount(ptr - pre[u]) != 1) {
ptr++;
}
pst[u] = ptr;
cerr << u << ": " << pre[u] << ' ' << pst[u] << '\n';
ptr += pst[u] - pre[u];
for (auto [v, id] : adj[u]) {
if (v == p[u].FI) continue;
dfs(v);
}
}
void fwincre(int i, int x, int *fw) {
for (; i <= MAXD; i += i & -i) fw[i] = (ll) fw[i] * x % l;
}
int fwqry(int i, int *fw) {
int res = 1;
for (; i > 0; i -= i & -i) res = (ll) res * fw[i] % l;
return res;
}
int st[MAXN * 4][MAXD + 1];
void incre(int p, int l, int x, int lo, int hi) {
int m = hi - lo;
int u = p + m;
while (u >= lo) {
fwincre(l, x, st[u]);
u >>= 1;
}
}
int qry(int s, int e, int l, int lo, int hi) {
int m = hi - lo;
int a = s + m, b = e + m;
int res = 1;
while (a < b) {
if (a & 1) {
res = (ll) res * fwqry(l, st[a]) % ::l;
a++;
}
if (b & 1) {
b--;
res = (ll) res * fwqry(l, st[b]) % ::l;
}
a >>= 1; b >>= 1;
}
return res;
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> n >> l;
REP (i, 1, n) {
int a, b; cin >> a >> b;
adj[a].pb({b, 0});
adj[b].pb({a, 0});
}
int on = n;
REP (i, 2, n + 1) {
if (adj[i].size() == 1) {
adj[i].pb({++on, 0});
adj[on].pb({i, 0});
}
}
dfs(1);
assert(ptr < MAXN * 4);
REP (i, 0, MAXN * 4) {
REP (j, 0, MAXD + 1) {
st[i][j] = 1;
}
}
REP (i, 1, n + 1) {
cin >> h[i];
}
cin >> q;
while (q--) {
int t; cin >> t;
if (t == 1) {
int x, d, w; cin >> x >> d >> w;
int u = x;
REP (i, MAXD - d + 1, MAXD + 1) {
if (p[u].FI == 0) break;
int id = p[u].SE;
u = p[u].FI;
cerr << "+ " << id << ' ' << i << ' ' << w << ' ' << pre[u] << ' ' << pst[u] << '\n';
incre(id, i, w, pre[u], pst[u]);
}
u = x;
REP (i, MAXD - d, MAXD + 1) {
if (adj[u][0].FI == p[u].FI) break;
int id = adj[u][0].SE;
cerr << "+ " << id << ' ' << i << ' ' << w << ' ' << pre[u] << ' ' << pst[u] << '\n';
incre(id, i, w, pre[u], pst[u]);
u = adj[u][0].FI;
}
} else {
int x; cin >> x;
int ans = h[x];
ans = (ll) ans * qry(pre[x], pst[x], MAXD, pre[x], pst[x]) % l;
int u = x;
RREP (i, MAXD - 1, 1) {
if (p[u].FI == 0) break;
int id = p[u].SE;
u = p[u].FI;
ans = (ll) ans * qry(pre[u], id, i, pre[u], pst[u]) % l;
ans = (ll) ans * qry(id + 1, pst[u], i, pre[u], pst[u]) % l;
}
cout << ans << '\n';
}
}
return 0;
}
/*
6 10
5 6
1 2
1 4
2 6
3 6
9
2
3
4
9
1
2
1 4 1 9
2 1
4 7
1 2
2 3
3 4
1
1
1
1
2
1 1 0 2
2 1
*/
Compilation message
sprinkler.cpp: In function 'void dfs(int)':
sprinkler.cpp:16:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
51 | REP (i, 0, adj[u].size()) {
| ~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:51:5: note: in expansion of macro 'REP'
51 | REP (i, 0, adj[u].size()) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
272720 KB |
Output is correct |
| 2 |
Correct |
108 ms |
272720 KB |
Output is correct |
| 3 |
Correct |
114 ms |
272700 KB |
Output is correct |
| 4 |
Correct |
112 ms |
272788 KB |
Output is correct |
| 5 |
Incorrect |
112 ms |
272708 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
272644 KB |
Output is correct |
| 2 |
Incorrect |
1627 ms |
290960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
272644 KB |
Output is correct |
| 2 |
Incorrect |
1627 ms |
290960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
272740 KB |
Output is correct |
| 2 |
Correct |
1287 ms |
292824 KB |
Output is correct |
| 3 |
Execution timed out |
4070 ms |
289924 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
272712 KB |
Output is correct |
| 2 |
Correct |
1288 ms |
292488 KB |
Output is correct |
| 3 |
Execution timed out |
4075 ms |
288304 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
272720 KB |
Output is correct |
| 2 |
Correct |
108 ms |
272720 KB |
Output is correct |
| 3 |
Correct |
114 ms |
272700 KB |
Output is correct |
| 4 |
Correct |
112 ms |
272788 KB |
Output is correct |
| 5 |
Incorrect |
112 ms |
272708 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
