#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
const int N = 2e5;
long long h[N+5];
int n, l;
vector<int> adj[N+5];
bool vis[N+5][45];
void dfs (int u, int prv, long long w, int dst) {
if (dst < 0) return;
h[u] *= w;
h[u] %= l;
//cerr << u << " lalala " << h[u] << endl;
for (int v : adj[u]) {
if (v==prv) continue;
dfs(v, u, w, dst-1);
}
}
void dfs4 (int u, int prv, long long w, int dst) {
if (dst < 0) return;
if (vis[u][dst]) return;
vis[u][dst] = true;
h[u] *= w;
h[u] %= l;
//cerr << u << " lalala " << h[u] << endl;
for (int v : adj[u]) {
if (v==prv) continue;
dfs4(v, u, w, dst-1);
}
}
int lst[N+5];
int sqr;
int mul (ll a, ll b) {
int res = (a*b) % l;
return res;
}
long long ht[N+5];
void dfs2 (int u, int prv, long long w, int dst) {
ht[u] = mul(ht[u], w);
if (dst == 0) return;
//cerr << u << " lalala " << h[u] << endl;
if (dst==1 && adj[u].size() < sqr) {
for (int v : adj[u]) {
if (v==prv) continue;
dfs2(v, u, w, dst-1);
}
}
}
void sub2() {
int q; cin>>q;
sqr = sqrt(n);
for(int i=1; i<=n; i++) {
ht[i] = 1;
}
for(int tm = 1; tm <= q; tm++) {
int tp;
cin >> tp;
if (tp == 1) {
int x, d, w;
cin >> x >> d >> w;
if (d == 0) h[x] = mul(h[x], w);
else dfs2(x, 0, w, d);
} else {
int x;
cin >> x;
ll res = mul(h[x], ht[x]);
if (adj[x].size() < sqr) {
for (int u : adj[x]) {
res = mul(res, ht[u]);
}
}
cout << res << endl;
}
}
}
void sub4() {
int q; cin>>q;
while (q--) {
int tp;
cin >> tp;
if (tp == 1) {
int x, d, w;
cin >> x >> d >> w;
dfs4(x, 0, w, d);
} else {
int x;
cin >> x;
cout << h[x] << endl;
}
}
}
void sub1() {
int q; cin>>q;
while (q--) {
int tp;
cin >> tp;
if (tp == 1) {
int x, d, w;
cin >> x >> d >> w;
dfs(x, 0, w, d);
} else {
int x;
cin >> x;
cout << h[x] << endl;
}
}
}
signed main () {
int t=1;
//scanf("%d", &t);
while(t--) {
cin >> n >> l;
for(int i=1; i<n; i++) {
int a, b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
for (int i=1; i<=n; i++) {
cin >> h[i];
}
if (n <= 1000) sub1();
else sub4();
}
}
Compilation message
sprinkler.cpp: In function 'void dfs2(int, int, long long int, int)':
sprinkler.cpp:55:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
55 | if (dst==1 && adj[u].size() < sqr) {
| ~~~~~~~~~~~~~~^~~~~
sprinkler.cpp: In function 'void sub2()':
sprinkler.cpp:81:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
81 | if (adj[x].size() < sqr) {
| ~~~~~~~~~~~~~~^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
7 ms |
4948 KB |
Output is correct |
5 |
Correct |
5 ms |
4948 KB |
Output is correct |
6 |
Correct |
9 ms |
5064 KB |
Output is correct |
7 |
Correct |
9 ms |
4948 KB |
Output is correct |
8 |
Correct |
8 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4976 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
5 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
5012 KB |
Output is correct |
19 |
Correct |
3 ms |
4900 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
4948 KB |
Output is correct |
23 |
Correct |
4 ms |
4948 KB |
Output is correct |
24 |
Correct |
3 ms |
4948 KB |
Output is correct |
25 |
Correct |
3 ms |
4948 KB |
Output is correct |
26 |
Correct |
3 ms |
4988 KB |
Output is correct |
27 |
Correct |
3 ms |
4948 KB |
Output is correct |
28 |
Correct |
5 ms |
4948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Incorrect |
766 ms |
25328 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Incorrect |
766 ms |
25328 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
991 ms |
22452 KB |
Output is correct |
3 |
Correct |
719 ms |
21936 KB |
Output is correct |
4 |
Correct |
1006 ms |
22208 KB |
Output is correct |
5 |
Correct |
1181 ms |
22332 KB |
Output is correct |
6 |
Correct |
1190 ms |
22480 KB |
Output is correct |
7 |
Correct |
1270 ms |
22524 KB |
Output is correct |
8 |
Correct |
936 ms |
22984 KB |
Output is correct |
9 |
Correct |
1041 ms |
22720 KB |
Output is correct |
10 |
Correct |
764 ms |
21940 KB |
Output is correct |
11 |
Correct |
980 ms |
22680 KB |
Output is correct |
12 |
Correct |
813 ms |
21952 KB |
Output is correct |
13 |
Correct |
754 ms |
22820 KB |
Output is correct |
14 |
Correct |
745 ms |
23292 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
4 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Incorrect |
921 ms |
25372 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
7 ms |
4948 KB |
Output is correct |
5 |
Correct |
5 ms |
4948 KB |
Output is correct |
6 |
Correct |
9 ms |
5064 KB |
Output is correct |
7 |
Correct |
9 ms |
4948 KB |
Output is correct |
8 |
Correct |
8 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4976 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
5 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
5012 KB |
Output is correct |
19 |
Correct |
3 ms |
4900 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
4948 KB |
Output is correct |
23 |
Correct |
4 ms |
4948 KB |
Output is correct |
24 |
Correct |
3 ms |
4948 KB |
Output is correct |
25 |
Correct |
3 ms |
4948 KB |
Output is correct |
26 |
Correct |
3 ms |
4988 KB |
Output is correct |
27 |
Correct |
3 ms |
4948 KB |
Output is correct |
28 |
Correct |
5 ms |
4948 KB |
Output is correct |
29 |
Correct |
2 ms |
4948 KB |
Output is correct |
30 |
Incorrect |
766 ms |
25328 KB |
Output isn't correct |
31 |
Halted |
0 ms |
0 KB |
- |