#include<bits/stdc++.h>
#define X first
#define Y second
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, b, a) for (int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define MASK(x) (1LL << (x))
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;
template<class A, class B>
bool maximize(A& x, B y) {
if (x < y) return x = y, true; else return false;
}
template<class A, class B>
bool minimize(A& x, B y) {
if (x > y) return x = y, true; else return false;
}
/* END OF TEMPLATE */
const int N = 2e3 + 7;
int n, mod, P[N], pos[N];
ll res[N][50], h[N], res2[N][50];
vector<int> v[N];
struct SegmentTree {
struct Node {
ll lazy, val;
Node() {
val = 1;
}
} st[4 * N];
ll mul(ll a, ll b) {
if (b == 0) return 1;
ll tmp = mul(a, b / 2);
tmp = tmp * tmp % mod;
if (b & 1) tmp = tmp * a % mod;
return tmp;
}
void Up(int id, int l, int r) {
if (l == r) return ;
st[id].val = st[id * 2].val * st[id * 2 + 1].val % mod;
}
void update(int id, int l, int r, int i, ll x) {
if (l > i || r < i) return ;
if (l == r) {
st[id].val = st[id].val * x % mod;
return ;
}
int mid = (l + r) >> 1;
update(id * 2, l, mid, i, x);
update(id * 2 + 1, mid + 1, r, i, x);
Up(id, l, r);
}
ll Get(int id, int l, int r, int u, int v) {
if (l > v || r < u || l > r) return 1;
if (u <= l && r <= v) return st[id].val;
int mid = (l + r) >> 1;
return Get(id * 2, l, mid, u, v) * Get(id * 2 + 1, mid + 1, r, u, v) % mod;
}
} st[42];
void dfs(int x, int par) {
P[x] = par;
for (auto y : v[x])
if (y != par) dfs(y, x);
}
void firstQuery() {
int x, d, w;
cin>>x>>d>>w;
FOR(j, 0, d) res2[x][j] = res2[x][j] * w % mod;
int tmp = 0;
while (x != -1 && tmp <= d) {
st[d - tmp].update(1, 1, n, pos[x], w);
res[x][d - tmp] = res[x][d - tmp] * w % mod;
tmp++;
x = P[x];
}
}
void secondQuery() {
int x;
cin>>x;
ll ans = h[x];
int tmp = 1;
int last_x = x;
// ans = ans * res2[x][0] % mod;
FOR(i, 0, 40) ans = ans * res[x][i] % mod;
x = P[x];
// cout<<res[2][1]<<"\n";
// cout <<x<<" "<<ans<<"\n";
while (x != -1 && tmp <= 40) {
ans = ans * res2[x][tmp] % mod;
// cout<<x<<" "<<ans<<"\n";
// ans = ans * res[x][0] % mod;
if (tmp < 40) {
int t = lower_bound(all(v[x]), last_x) - v[x].begin();
if (t < (int)v[x].size()) {
FOR(j, tmp + 1, 40) {
ans = ans * st[j].Get(1, 1, n, pos[v[x][0]], pos[v[x][t]] - 1) % mod;
ans = ans * st[j].Get(1, 1, n, pos[v[x][t]] + 1, pos[v[x].back()]) % mod;
}
}
// for (auto y : v[x])
// if (y != last_x && y != P[x]) {
// FOR(j, 0, 40)
// if (j >= tmp + 1) {
// ans = ans * res[y][j] % mod;
//// cout<<y<<" "<<j<<" "<<res[y][j]<<"\n";
// }
// }
}
// cout<<x<<" "<<ans<<"\n";
// break;
last_x = x;
x = P[x];
tmp++;
}
cout<<ans<<"\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>mod;
REP(i, 1, n) {
int x, y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
FOR(i, 1, n)
FOR(j, 0, 40) res[i][j] = res2[i][j] = 1;
FOR(i, 1, n) cin>>h[i];
dfs(1, -1);
FOR(i, 1, n) {
vector<int> a;
for (auto x : v[i])
if (x != P[i]) a.push_back(x);
v[i] = a;
sort(all(v[i]));
}
int cnt = 0;
FOR(i, 1, n)
for (auto x : v[i]) pos[x] = ++cnt;
int Q;
cin>>Q;
while (Q--) {
int type;
cin>>type;
if (type == 1) firstQuery(); else secondQuery();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5588 KB |
Output is correct |
2 |
Correct |
3 ms |
5588 KB |
Output is correct |
3 |
Correct |
2 ms |
5588 KB |
Output is correct |
4 |
Correct |
45 ms |
6508 KB |
Output is correct |
5 |
Correct |
45 ms |
6508 KB |
Output is correct |
6 |
Correct |
24 ms |
6528 KB |
Output is correct |
7 |
Correct |
20 ms |
6532 KB |
Output is correct |
8 |
Correct |
9 ms |
6484 KB |
Output is correct |
9 |
Correct |
3 ms |
5664 KB |
Output is correct |
10 |
Correct |
3 ms |
5660 KB |
Output is correct |
11 |
Correct |
4 ms |
5588 KB |
Output is correct |
12 |
Correct |
6 ms |
5588 KB |
Output is correct |
13 |
Correct |
5 ms |
5588 KB |
Output is correct |
14 |
Correct |
3 ms |
5588 KB |
Output is correct |
15 |
Correct |
3 ms |
5660 KB |
Output is correct |
16 |
Correct |
4 ms |
5588 KB |
Output is correct |
17 |
Correct |
5 ms |
5588 KB |
Output is correct |
18 |
Correct |
8 ms |
5588 KB |
Output is correct |
19 |
Correct |
4 ms |
5588 KB |
Output is correct |
20 |
Correct |
4 ms |
5588 KB |
Output is correct |
21 |
Correct |
4 ms |
5588 KB |
Output is correct |
22 |
Correct |
6 ms |
5716 KB |
Output is correct |
23 |
Correct |
6 ms |
5660 KB |
Output is correct |
24 |
Correct |
3 ms |
5588 KB |
Output is correct |
25 |
Correct |
3 ms |
5656 KB |
Output is correct |
26 |
Correct |
4 ms |
5588 KB |
Output is correct |
27 |
Correct |
5 ms |
5656 KB |
Output is correct |
28 |
Correct |
5 ms |
5656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5588 KB |
Output is correct |
2 |
Runtime error |
7 ms |
11220 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5588 KB |
Output is correct |
2 |
Runtime error |
7 ms |
11220 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5588 KB |
Output is correct |
2 |
Runtime error |
8 ms |
11188 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5588 KB |
Output is correct |
2 |
Runtime error |
7 ms |
11264 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5588 KB |
Output is correct |
2 |
Correct |
3 ms |
5588 KB |
Output is correct |
3 |
Correct |
2 ms |
5588 KB |
Output is correct |
4 |
Correct |
45 ms |
6508 KB |
Output is correct |
5 |
Correct |
45 ms |
6508 KB |
Output is correct |
6 |
Correct |
24 ms |
6528 KB |
Output is correct |
7 |
Correct |
20 ms |
6532 KB |
Output is correct |
8 |
Correct |
9 ms |
6484 KB |
Output is correct |
9 |
Correct |
3 ms |
5664 KB |
Output is correct |
10 |
Correct |
3 ms |
5660 KB |
Output is correct |
11 |
Correct |
4 ms |
5588 KB |
Output is correct |
12 |
Correct |
6 ms |
5588 KB |
Output is correct |
13 |
Correct |
5 ms |
5588 KB |
Output is correct |
14 |
Correct |
3 ms |
5588 KB |
Output is correct |
15 |
Correct |
3 ms |
5660 KB |
Output is correct |
16 |
Correct |
4 ms |
5588 KB |
Output is correct |
17 |
Correct |
5 ms |
5588 KB |
Output is correct |
18 |
Correct |
8 ms |
5588 KB |
Output is correct |
19 |
Correct |
4 ms |
5588 KB |
Output is correct |
20 |
Correct |
4 ms |
5588 KB |
Output is correct |
21 |
Correct |
4 ms |
5588 KB |
Output is correct |
22 |
Correct |
6 ms |
5716 KB |
Output is correct |
23 |
Correct |
6 ms |
5660 KB |
Output is correct |
24 |
Correct |
3 ms |
5588 KB |
Output is correct |
25 |
Correct |
3 ms |
5656 KB |
Output is correct |
26 |
Correct |
4 ms |
5588 KB |
Output is correct |
27 |
Correct |
5 ms |
5656 KB |
Output is correct |
28 |
Correct |
5 ms |
5656 KB |
Output is correct |
29 |
Correct |
2 ms |
5588 KB |
Output is correct |
30 |
Runtime error |
7 ms |
11220 KB |
Execution killed with signal 11 |
31 |
Halted |
0 ms |
0 KB |
- |