#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxq = 4e5 + 10;
struct query
{
int type, ver, d, t;
ll w;
}ask[maxq];
const int maxn = 2e5 + 10;
int n, q;
ll l, h[maxn];
vector < query > task[maxn];
vector < int > adj[maxn];
bool cmp(query a1, query a2)
{
return a1.d < a2.d;
}
void input()
{
cin >> n >> l;
for (int i = 1; i < n; i ++)
{
int v, u;
cin >> v >> u;
adj[v].push_back(u);
adj[u].push_back(v);
}
for (int i = 1; i <= n; i ++)
cin >> h[i];
cin >> q;
for (int i = 1; i <= q; i ++)
{
cin >> ask[i].type;
if (ask[i].type == 1)
cin >> ask[i].ver >> ask[i].d >> ask[i].w;
else
cin >> ask[i].ver;
ask[i].t = i;
}
}
struct segment_tree
{
vector < ll > tree, lazy;
segment_tree(int len = 0)
{
tree.resize(4 * (len + 1));
lazy.resize(4 * (len + 1));
fill(tree.begin(), tree.end(), 1);
fill(lazy.begin(), lazy.end(), 1);
}
void push_lazy(int root, int left, int right)
{
tree[root] *= lazy[root];
if (left != right)
{
lazy[root * 2] *= (lazy[root]);
lazy[root * 2 + 1] *= (lazy[root]);
lazy[root * 2] %= l;
lazy[root * 2 + 1] %= l;
}
lazy[root] = 1;
}
void update_range(int root, int left, int right, int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] = val;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
update_range(root * 2, left, mid, qleft, qright, val);
update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);
}
ll get_point(int root, int left, int right, int pos)
{
push_lazy(root, left, right);
if (left == right)
return tree[root];
int mid = (left + right) / 2;
if (pos <= mid)
return get_point(root * 2, left, mid, pos);
return get_point(root * 2 + 1, mid + 1, right, pos);
}
};
segment_tree st[maxn];
int par[maxn], depth[maxn];
vector < int > by_depth[maxn];
int tin[maxn], tout[maxn], timer, rev[maxn];
void dfs(int v)
{
tin[v] = ++ timer;
///cout << "dfs " << v << " " << depth[v] << endl;
rev[v] = by_depth[depth[v]].size();
by_depth[depth[v]].push_back(v);
for (int u : adj[v])
{
if (u == par[v])
continue;
par[u] = v;
depth[u] = depth[v] + 1;
dfs(u);
}
tout[v] = timer;
}
const int maxd = 40;
void update_row(int row, int left, int right, ll val)
{
int lf = 0, rf = (int)(by_depth[row].size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (tin[by_depth[row][mf]] < left)
lf = mf + 1;
else
rf = mf - 1;
}
int lb = lf;
lf = 0;
rf = (int)(by_depth[row].size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (tin[by_depth[row][mf]] <= right)
lf = mf + 1;
else
rf = mf - 1;
}
int rb = rf;
st[row].update_range(1, 0, (int)(by_depth[row].size()) - 1, lb, rb, val);
/**for (int cur : by_depth[row])
{ ///cout << "vertex " << cur << endl;
if (tin[cur] >= lf && tin[cur] <= rf)
h[cur] = (h[cur] * val) % l;
}*/
}
void make_query(int v)
{
ll ans = h[v];
ans = ans * st[depth[v]].get_point(1, 0, (int)(by_depth[depth[v]].size()) - 1, rev[v]);
ans %= l;
cout << ans << endl;
}
void simulate()
{
for (int i = 1; i <= n; i ++)
st[i] = segment_tree(by_depth[i].size());
for (int i = 1; i <= q; i ++)
{
if (ask[i].type == 2)
make_query(ask[i].ver);
else
{
int cnt = 0, ver = ask[i].ver;
while(ver != 1 && cnt <= ask[i].d)
{
int lf = ask[i].d - cnt;
update_row(depth[ver] + lf, tin[ver], tout[ver], ask[i].w);
///cout << "update " << ver << " " << depth[ver] + lf << endl;
//if (lf != 0)
update_row(depth[ver] + lf - 1, tin[ver], tout[ver], ask[i].w);
cnt ++;
ver = par[ver];
}
if (ver == 1 && cnt <= ask[i].d)
{
int lf = ask[i].d - cnt;
for (int j = 0; j <= lf; j ++)
{
///cout << "update " << ver << " " << depth[ver] + j << endl;
update_row(depth[ver] + j, tin[ver], tout[ver], ask[i].w);
}
}
/**for (int i = 1; i <= n; i ++)
cout << h[i] << " ";
cout << endl;*/
}
}
}
void solve()
{
input();
///offline_queries();
depth[1] = 1;
dfs(1);
simulate();
}
int main()
{
speed();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
47964 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47912 KB |
Output is correct |
| 3 |
Correct |
25 ms |
47932 KB |
Output is correct |
| 4 |
Incorrect |
26 ms |
48220 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
47964 KB |
Output is correct |
| 2 |
Incorrect |
380 ms |
85456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
47964 KB |
Output is correct |
| 2 |
Incorrect |
380 ms |
85456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
47852 KB |
Output is correct |
| 2 |
Correct |
497 ms |
99412 KB |
Output is correct |
| 3 |
Correct |
1946 ms |
95412 KB |
Output is correct |
| 4 |
Correct |
741 ms |
96036 KB |
Output is correct |
| 5 |
Correct |
3389 ms |
82812 KB |
Output is correct |
| 6 |
Correct |
2316 ms |
86512 KB |
Output is correct |
| 7 |
Correct |
1176 ms |
86696 KB |
Output is correct |
| 8 |
Correct |
311 ms |
87260 KB |
Output is correct |
| 9 |
Correct |
511 ms |
98008 KB |
Output is correct |
| 10 |
Correct |
1578 ms |
102132 KB |
Output is correct |
| 11 |
Correct |
1518 ms |
86640 KB |
Output is correct |
| 12 |
Execution timed out |
4085 ms |
87388 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
47964 KB |
Output is correct |
| 2 |
Correct |
544 ms |
96248 KB |
Output is correct |
| 3 |
Incorrect |
2000 ms |
91524 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
47964 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47912 KB |
Output is correct |
| 3 |
Correct |
25 ms |
47932 KB |
Output is correct |
| 4 |
Incorrect |
26 ms |
48220 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
