This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXD = 40;
const int MAXN = 200000;
int MOD = 0;
vector <int> g[MAXN + 5];
int height[MAXN + 5], position[MAXN + 5], parent[MAXN + 5], start_height[MAXN + 5], rows[MAXN + 5];
pair <int, int> subtree[MAXD + 5][MAXN + 5];
vector <int> tree[MAXN + 5];
deque <pair <pair <int, int>, int> > ququ[MAXN + 5];
void dfs(int v, int pr, int hei)
{
parent[v] = pr;
height[v] = hei;
position[v] = rows[hei];
rows[hei]++;
int pos = -1;
for (int i = 0; i < (int) g[v].size(); i++)
if (g[v][i] == pr) pos = i;
if (pos != -1)
{
swap(g[v][pos], g[v].back());
g[v].pop_back();
}
for (int u : g[v])
dfs(u, v, hei + 1);
subtree[0][v] = mp(position[v], position[v]);
if (!g[v].empty())
{
subtree[1][v] = mp(position[g[v][0]], position[g[v].back()]);
int lef = 0, rig = (int) g[v].size() - 1;
for (int i = 2; i <= MAXD; i++)
{
while (lef <= rig && subtree[i - 1][g[v][lef]] == mp(-1, -1)) lef++;
while (lef <= rig && subtree[i - 1][g[v][rig]] == mp(-1, -1)) rig--;
if (lef <= rig) subtree[i][v] = mp(subtree[i - 1][g[v][lef]].x, subtree[i - 1][g[v][rig]].y);
else break;
}
}
return;
}
int get_height(vector <int> &tree, int v, int lef, int rig, int pos, int cur_val)
{
if (tree[v] != 1) cur_val = (ll) cur_val * (ll) tree[v] % (ll) MOD;
if (cur_val == 0) return 0;
if (lef == rig) return cur_val;
int mid = (lef + rig) / 2;
if (pos <= mid) return get_height(tree, 2 * v, lef, mid, pos, cur_val);
else return get_height(tree, 2 * v + 1, mid + 1, rig, pos, cur_val);
}
void update(vector <int> &tree, int v, int lef, int rig, int A, int B, int mn)
{
if (lef > B || rig < A) return;
if (A <= lef && rig <= B)
{
tree[v] = (ll) tree[v] * (ll) mn % (ll) MOD;
return;
}
int mid = (lef + rig) / 2;
if (tree[v] != 1)
{
tree[2 * v] = (ll) tree[2 * v] * (ll) tree[v] % (ll) MOD;
tree[2 * v + 1] = (ll) tree[2 * v + 1] * (ll) tree[v] % (ll) MOD;
tree[v] = 1;
}
update(tree, 2 * v, lef, mid, A, B, mn);
update(tree, 2 * v + 1, mid + 1, rig, A, B, mn);
return;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int n, mod;
cin >> n >> mod;
MOD = mod;
for (int i = 0; i <= MAXD; i++)
for (int j = 1; j <= n; j++)
subtree[i][j] = mp(-1, -1);
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
for (int i = 1; i <= n; i++) cin >> start_height[i];
dfs(1, -1, 0);
{
int h = 0;
while (rows[h] > 0)
{
tree[h].resize(4 * rows[h], 1);
h++;
}
}
int quer;
cin >> quer;
for (int rep = 1; rep <= quer; rep++)
{
int typ;
cin >> typ;
if (typ == 1)
{
int vert, dist, mn;
cin >> vert >> dist >> mn;
int cur = 0, curv = vert;
for (int fin = height[vert] + dist; fin >= height[vert] - dist; fin--)
{
int x = (dist + height[vert] - fin) / 2;
if (x > cur)
{
if (parent[curv] != -1) curv = parent[curv], cur++;
}
if (height[curv] > fin) break;
int y = fin - height[curv];
pair <int, int> bounds = subtree[y][curv];
if (bounds.x == -1) continue;
if (mn != 1) ququ[fin].pb(mp(mp(bounds.x, bounds.y), mn));
}
}
else
{
int vert;
cin >> vert;
int heh = height[vert];
while (!ququ[heh].empty())
{
pair <pair <int, int>, int> A = ququ[heh].front();
ququ[heh].pop_front();
update(tree[heh], 1, 0, rows[heh] - 1, A.x.x, A.x.y, A.y);
}
int ans = get_height(tree[heh], 1, 0, rows[heh] - 1, position[vert], 1);
ans = (ll) ans * (ll) start_height[vert] % (ll) MOD;
cout << ans << '\n';
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |