Pagini recente » Cod sursa (job #3340396) | Cod sursa (job #951561) | Monitorul de evaluare | Cod sursa (job #3354879) | Cod sursa (job #3354491)
#include <bits/stdc++.h>
using namespace std;
const int N = 32001, E = 16;
int anc[E][N], mn[E][N]; // stramosul/minimul de la j urcat cu 2**e nivele
int lvl[N], lg[N];
int n, m, p;
int x, y, a, b, c, d, z = 1e9;
vector<pair<int, int>> mc[N];
void dfs(int nod) {
for (auto& i : mc[nod]) {
lvl[i.first] = lvl[nod] + 1;
dfs(i.first);
}
}
int get_anc(int nod, int ord) {
for (int bit = 0; (1 << bit) <= ord; ++bit) {
if ((1 << bit) & ord) {
nod = anc[bit][nod];
}
}
return nod;
}
int get_min(int nod, int ord) {
int minimum = 1e9;
for (int bit = 0; (1 << bit) <= ord; ++bit) {
if ((1 << bit) & ord) {
minimum = min(minimum, mn[bit][nod]);
nod = anc[bit][nod];
}
}
return minimum;
}
void lca(int x, int y, int& z) {
int ord = lg[lvl[x]];
while (ord >= 0) {
if (anc[ord][x] != anc[ord][y]) {
z = min(z, min(mn[ord][x], mn[ord][y]));
x = anc[ord][x];
y = anc[ord][y];
}
--ord;
}
z = min(z, min(mn[0][x], mn[0][y]));
if (m < p)
cout << z << '\n';
}
int main() {
freopen("atac.in", "r", stdin);
freopen("atac.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> p;
for (int i = 2; i <= n; ++i) {
int nod, cost;
cin >> nod >> cost;
mc[nod].push_back({ i, cost });
anc[0][i] = nod;
mn[0][i] = cost;
}
cin >> x >> y >> a >> b >> c >> d;
for (int i = 2; i < N; ++i) lg[i] = lg[i / 2] + 1;
int rad = anc[0][1];
if (rad == 0) rad = 1;
while (anc[0][rad]) rad = anc[0][rad];
dfs(rad);
for (int e = 1; e < E; ++e) {
for (int i = 1; i <= n; ++i) {
anc[e][i] = anc[e - 1][anc[e - 1][i]];
mn[e][i] = min(mn[e - 1][i], mn[e - 1][anc[e - 1][i]]);
}
}
while (m--) {
if (x == y) {
z = 0;
}
else if (lvl[x] < lvl[y]) {
z = get_min(y, lvl[y] - lvl[x]);
y = get_anc(y, lvl[y] - lvl[x]);
}
else if (lvl[y] < lvl[x]) {
z = get_min(x, lvl[x] - lvl[y]);
x = get_anc(x, lvl[x] - lvl[y]);
}
if (x == y) {
if (m < p)
cout << z << '\n';
}
else {
lca(x, y, z);
}
x = (x * a + y * b) % n + 1;
y = (y * c + z * d) % n + 1;
z = 1e9;
}
return 0;
}