#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100005];
long long h[100005];
long long parent[100005];
long long mul[100005][45];
int mod;
void dfs(int x,int p){
for(auto u:adj[x]){
if(u==p) continue;
parent[u]=x;
dfs(u,x);
}
return;
}
void update(int x,int d,int w){
if(d==-1)return;
if(x==0){
for (int i = 0; i <= d; ++i)
{
mul[x][i]=mul[x][i]*w%mod;
}
//if(x==0) cout <<"nav"<<" "<<mul[0][0]<<endl;
return;
}
update(parent[x],d-1,w);
mul[x][d]=mul[x][d]*w%mod;
if(d) mul[x][d-1]=mul[x][d-1]*w%mod;
}
long long query(int x)
{
long long ans=h[x];
int cur=x;
for (int i = 0; i <= 40; ++i)
{
ans=ans*mul[cur][i]%mod;
if(cur==0) return ans;
cur=parent[cur];
}
return ans;
}
int main() {
int n;
cin>>n>>mod;
for (int i = 0; i < n-1; ++i)
{
int x,y;
cin>>x>>y;
x--;y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < 41; ++j)
{
mul[i][j]=1;
}
cin>>h[i];
}
dfs(0,-1);
int q;
cin>>q;
while(q--){
int c;
cin>>c;
if(c==1){
int x,d,w;
cin>>x>>d>>w;
x--;
update(x,d,w);
}else{
int x;
cin>>x;
x--;
cout << query(x)<<endl;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
5 ms |
6748 KB |
Output is correct |
5 |
Correct |
4 ms |
6572 KB |
Output is correct |
6 |
Correct |
5 ms |
6748 KB |
Output is correct |
7 |
Correct |
4 ms |
6748 KB |
Output is correct |
8 |
Correct |
4 ms |
6808 KB |
Output is correct |
9 |
Correct |
2 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4524 KB |
Output is correct |
11 |
Correct |
2 ms |
4440 KB |
Output is correct |
12 |
Correct |
3 ms |
4444 KB |
Output is correct |
13 |
Correct |
3 ms |
4444 KB |
Output is correct |
14 |
Correct |
3 ms |
4444 KB |
Output is correct |
15 |
Correct |
3 ms |
4444 KB |
Output is correct |
16 |
Correct |
2 ms |
4520 KB |
Output is correct |
17 |
Correct |
2 ms |
4444 KB |
Output is correct |
18 |
Correct |
4 ms |
4444 KB |
Output is correct |
19 |
Correct |
2 ms |
4444 KB |
Output is correct |
20 |
Correct |
2 ms |
4440 KB |
Output is correct |
21 |
Correct |
2 ms |
4444 KB |
Output is correct |
22 |
Correct |
3 ms |
4444 KB |
Output is correct |
23 |
Correct |
3 ms |
4444 KB |
Output is correct |
24 |
Correct |
2 ms |
4444 KB |
Output is correct |
25 |
Correct |
2 ms |
4444 KB |
Output is correct |
26 |
Correct |
2 ms |
4444 KB |
Output is correct |
27 |
Correct |
2 ms |
4444 KB |
Output is correct |
28 |
Correct |
2 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4444 KB |
Output is correct |
2 |
Runtime error |
5 ms |
8648 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4444 KB |
Output is correct |
2 |
Runtime error |
5 ms |
8648 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Runtime error |
5 ms |
8796 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Runtime error |
6 ms |
8796 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
5 ms |
6748 KB |
Output is correct |
5 |
Correct |
4 ms |
6572 KB |
Output is correct |
6 |
Correct |
5 ms |
6748 KB |
Output is correct |
7 |
Correct |
4 ms |
6748 KB |
Output is correct |
8 |
Correct |
4 ms |
6808 KB |
Output is correct |
9 |
Correct |
2 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4524 KB |
Output is correct |
11 |
Correct |
2 ms |
4440 KB |
Output is correct |
12 |
Correct |
3 ms |
4444 KB |
Output is correct |
13 |
Correct |
3 ms |
4444 KB |
Output is correct |
14 |
Correct |
3 ms |
4444 KB |
Output is correct |
15 |
Correct |
3 ms |
4444 KB |
Output is correct |
16 |
Correct |
2 ms |
4520 KB |
Output is correct |
17 |
Correct |
2 ms |
4444 KB |
Output is correct |
18 |
Correct |
4 ms |
4444 KB |
Output is correct |
19 |
Correct |
2 ms |
4444 KB |
Output is correct |
20 |
Correct |
2 ms |
4440 KB |
Output is correct |
21 |
Correct |
2 ms |
4444 KB |
Output is correct |
22 |
Correct |
3 ms |
4444 KB |
Output is correct |
23 |
Correct |
3 ms |
4444 KB |
Output is correct |
24 |
Correct |
2 ms |
4444 KB |
Output is correct |
25 |
Correct |
2 ms |
4444 KB |
Output is correct |
26 |
Correct |
2 ms |
4444 KB |
Output is correct |
27 |
Correct |
2 ms |
4444 KB |
Output is correct |
28 |
Correct |
2 ms |
4444 KB |
Output is correct |
29 |
Correct |
2 ms |
4444 KB |
Output is correct |
30 |
Runtime error |
5 ms |
8648 KB |
Execution killed with signal 11 |
31 |
Halted |
0 ms |
0 KB |
- |