#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
int N, L;
int qs, qe, n;
struct st
{
vector<long long>r;
int treeN;
void init(int cnt)
{
for (treeN = 1; treeN < cnt; treeN *= 2);
r.resize(2 * treeN -1, 1);
}
void upd(int s, int e, int i = 1)
{
if (s > qe || qs > e)
return;
if (qs <= s && e <= qe)
{
r[i] *= n;
if (r[i] >= L)
r[i] %= L;
return;
}
upd(s, (s + e) / 2, i * 2);
upd((s + e) / 2 + 1, e, i * 2 + 1);
}
int ge(int qs, int qe, int n, int i = 1)
{
if (qs == qe)
{
return r[i];
}
int m = (qs + qe) / 2;
if (n > m)
{
return r[i] * ge(m + 1, qe, n, i * 2 + 1) % L;
}
else
{
return r[i] * ge(qs, m, n, i * 2) % L;
}
}
}arr[200100];
int d[201000];
int pos[200100];
int par[200100];
int st[201000];
int en[200100];
int c;
vector<int>li[201000];
vector<pair<int, int>>dl[200100];
vector<int>dl2[200100];
void dfs(int n, int p = 0)
{
st[n] = ++c;
dl[d[n]].push_back({ st[n],n });
dl2[d[n]].push_back(st[n]);
int i;
for (i = 0; i < li[n].size(); i++)
{
if (li[n][i] == p)
continue;
par[li[n][i]] = n;
d[li[n][i]] = d[n] + 1;
dfs(li[n][i], n);
}
en[n] = c;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> L;
int i;
for (i = 1; i < N; i++)
{
int a, b;
cin >> a >> b;
li[a].push_back(b);
li[b].push_back(a);
}
dfs(1);
for (i = 0; i <= N; i++)
{
arr[i].init(dl[i].size());
int j;
for (j = 0; j < dl[i].size(); j++)
{
pos[dl[i][j].second] = j;
}
}
for (i = 1; i <= N; i++)
{
int a;
cin >> a;
arr[d[i]].r[pos[i] + arr[d[i]].treeN] = a;
}
int Q;
cin >> Q;
while (Q--)
{
int a;
cin >> a;
if (a == 1)
{
int b, c, w;
cin >> b >> c >> w;
int j;
int dp = d[b];
int cp = b;
for (j = dp + c; j >= dp - c; j--)
{
if (j + dp - d[cp] * 2 + 2 <= c && cp != 1)
{
cp = par[cp];
}
if (j < 0)
break;
int lp = lower_bound(dl2[j].begin(), dl2[j].end(), st[cp]) - dl2[j].begin();
if (lp != dl2[j].size() && dl2[j][lp] <= en[cp])
{
int rp = lower_bound(dl2[j].begin() + lp, dl2[j].end(), en[cp] + 1) - dl2[j].begin() - 1;
qs = lp;
qe = rp;
n = w;
arr[j].upd(0, arr[j].treeN - 1);
}
}
}
else
{
int b;
cin >> b;
cout << arr[d[b]].ge(0, arr[d[b]].treeN - 1, pos[b]) << '\n';
}
}
}
Compilation message
sprinkler.cpp: In function 'void dfs(int, int)':
sprinkler.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (i = 0; i < li[n].size(); i++)
| ~~^~~~~~~~~~~~~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:91:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (j = 0; j < dl[i].size(); j++)
| ~~^~~~~~~~~~~~~~
sprinkler.cpp:124:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | if (lp != dl2[j].size() && dl2[j][lp] <= en[cp])
| ~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
20692 KB |
Output is correct |
| 2 |
Runtime error |
35 ms |
41812 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
40 ms |
41800 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
40 ms |
41800 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
32 ms |
41780 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
20652 KB |
Output is correct |
| 2 |
Runtime error |
788 ms |
115032 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
20692 KB |
Output is correct |
| 2 |
Runtime error |
35 ms |
41812 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
