#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define f first
#define s second
#define pii pair <int,int>
#define en '\n'
void boos() {
ios_base :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int N = 4e5 + 100;
const int bl = 1000;
vector <int> g[N];
pair <int,pair <int,pair <int,ll> > > c[N];
ll a[N],L;
ll d[N][2];
map <int,bool> was[N];
int n;
void dfs(int v,int p) {
for(auto to : g[v]) {
if(to == p)continue;
d[to][0] = (d[to][0] * d[v][1]) % L;
d[v][0] = (d[v][0] * d[to][1]) % L;
dfs(to,v);
}
a[v] = (a[v] * d[v][0]) % L;
a[v] = (a[v] * d[v][1]) % L;
}
/*
4 7
1 2
2 3
3 4
1
1
1
1
6
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
*/
void solve() {
cin >> n >> L;
for(int i = 1;i <= n;i++) {
d[i][0] = 1;
d[i][1] = 1;
}
for(int i = 1;i < n;i++) {
int x,y;
cin >> x >> y;
was[x][y] = 1;
was[y][x] = 1;
g[x].pb(y);
g[y].pb(x);
}
for(int i = 1;i <= n;i++)cin >> a[i];
int q;
cin >> q;
int l = 1;
for(int i = 1;i <= q;i++) {
cin >> c[i].f;
if(c[i].f == 1)cin >> c[i].s.f >> c[i].s.s.f >> c[i].s.s.s;
else cin >> c[i].s.f;
if(i % bl == 0 || i == q) {
for(int j = l;j <= i;j++) {
if(c[j].f == 1) {
d[c[j].s.f][c[j].s.s.f] = (d[c[j].s.f][c[j].s.s.f] * c[j].s.s.s) % L;
continue;
}
ll ans = a[c[j].s.f];
//cout << ans << " ";
for(int h = l;h < j;h++) {
if(c[h].f == 1 && c[h].s.s.f >= (int)(c[j].s.f != c[h].s.f) && (c[j].s.f == c[h].s.f || was[c[j].s.f].count(c[h].s.f))) {
ans = (ans * c[h].s.s.s) % L;
//cout << h << " -- " << c[h].s.s.s << en;
}
}
cout << ans << en;
}
dfs(1,-1);
for(int j = 1;j <= n;j++) {
d[j][0] = 1;
d[j][1] = 1;
}
l = i + 1;
}
}
}
int main() {
boos();
int ttt;
ttt = 1;
while(ttt--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
28444 KB |
Output is correct |
| 2 |
Execution timed out |
4040 ms |
62668 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
28444 KB |
Output is correct |
| 2 |
Execution timed out |
4040 ms |
62668 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
28516 KB |
Output is correct |
| 2 |
Execution timed out |
4051 ms |
76896 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
28416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
28500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
