Pagini recente » Cod sursa (job #2770704) | Cod sursa (job #3166915) | Cod sursa (job #37256) | Cod sursa (job #3166902) | Cod sursa (job #3177711)
#include <bits/stdc++.h>
/// reimplementez
using namespace std;
const int max_size = 32e3 + 1, rmax = 16, INF = 2e9 + 1;
struct str{
int x, mn;
};
int lvl[max_size], lg[max_size], viz[max_size];
str t[rmax][max_size];
vector <pair <int, int>> mc[max_size];
void dfs (int nod)
{
viz[nod] = 1;
for (auto f : mc[nod])
{
if (viz[f.first])
{
continue;
}
lvl[f.first] = lvl[nod] + 1;
t[0][f.first].x = nod;
t[0][f.first].mn = f.second;
for (int e = 1; e < rmax; e++)
{
t[e][f.first].x = t[e - 1][t[e - 1][f.first].x].x;
t[e][f.first].mn = min(t[e - 1][f.first].mn, t[e - 1][t[e - 1][f.first].x].mn);
}
dfs(f.first);
}
}
int lca (int x, int y)
{
if (x == y)
{
return 0;
}
if (lvl[x] > lvl[y])
{
swap(x, y);
}
int ans = INF, dif = lvl[y] - lvl[x];
for (int e = 0; e < rmax; e++)
{
if ((dif & (1 << e)) != 0)
{
ans = min(ans, t[e][y].mn);
y = t[e][y].x;
}
}
if (x == y)
{
return ans;
}
for (int e = lg[lvl[x]]; e >= 0; e--)
{
if (t[e][x].x != t[e][y].x)
{
ans = min(ans, t[e][x].mn);
ans = min(ans, t[e][y].mn);
x = t[e][x].x;
y = t[e][y].x;
}
}
return min(ans, min(t[0][x].mn, t[0][y].mn));
}
signed main ()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#else
freopen("atac.in", "r", stdin);
freopen("atac.out", "w", stdout);
#endif // LOCAL
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q, p;
cin >> n >> q >> p;
for (int i = 2; i <= n; i++)
{
int x, c;
cin >> x >> c;
mc[x].push_back({i, c});
mc[i].push_back({x, c});
lg[i] = lg[i / 2] + 1;
}
for (int e = 0; e < rmax; e++)
{
t[e][1].x = 1;
t[e][1].mn = INF;
}
int x, y, a, b, c, d;
cin >> x >> y >> a >> b >> c >> d;
dfs(1);
while (q--)
{
int ans = lca(x, y);
x = (x * a + y * b) % n + 1;
y = (y * c + ans * d) % n + 1;
if (q < p)
{
cout << ans << '\n';
}
}
return 0;
}