Pagini recente » Cod sursa (job #1050741) | Cod sursa (job #1633907) | Cod sursa (job #2840272) | Cod sursa (job #470765) | Cod sursa (job #2446632)
#include <bits/stdc++.h>
using namespace std;
const int NMax = 32050;
const int LMax = 20;
int lvl[NMax];
pair < int, int > lift[LMax][NMax];
vector < vector < pair < int, int > > > G;
void DFS(int node, int father, int cost) {
for (auto x : G[node]) {
if (x.first == father) continue;
lvl[x.first] = lvl[node] + 1;
DFS(x.first, node, x.second);
}
lift[0][node] = {father, cost};
}
int lca(int x, int y) {
if (x == y) return 0;
assert(x > 0 && y > 0);
if (lvl[x] < lvl[y]) {
swap(x, y);
}
int logx, logy;
for (logx = 1; (1 << logx) < lvl[x]; ++logx);
for (logy = 1; (1 << logy) < lvl[y]; ++logy);
int mn = INT_MAX;
for (int i = logx; i >= 0; --i) {
if (lvl[x] - (1 << i) >= lvl[y]) {
mn = min(mn, lift[i][x].second);
x = lift[i][x].first;
}
}
if (x == y) return mn;
for (int i = logy; i >= 0; --i) {
if (lift[i][x].first != 0 && lift[i][x].first != lift[i][y].first) {
mn = min({mn, lift[i][x].second, lift[i][y].second});
x = lift[i][x].first;
y = lift[i][y].first;
}
}
return min({mn, lift[0][x].second, lift[0][y].second});
}
int main() {
ifstream cin("atac.in");
ofstream cout("atac.out");
int n, m, p;
cin >> n >> m >> p;
G.assign(n + 5, {});
for (int i = 2; i <= n; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back({i, v});
G[i].push_back({u, v});
}
DFS(1, 0, INT_MAX);
lift[0][0].second = INT_MAX;
for (int i = 1; i < LMax; ++i) {
for (int j = 0; j <= n; ++j) {
pair < int, int > next = lift[i - 1][lift[i - 1][j].first];
lift[i][j] = {next.first, min(lift[i - 1][j].second, next.second)};
}
}
long long x, y, a, b, c, d;
cin >> x >> y >> a >> b >> c >> d;
for (int i = 1; i <= m; ++i) {
long long z = lca(x, y);
if (i >= m - p + 1) {
cout << z << "\n";
}
int nx = (a * x + b * y) % n + 1;
int ny = (c * y + d * z) % n + 1;
x = nx; y = ny;
}
return 0;
}