Pagini recente » Cod sursa (job #2514039) | Cod sursa (job #723854) | Cod sursa (job #3237832) | Cod sursa (job #2945873) | Cod sursa (job #3269674)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
#define MAXN 32005
struct Edge {
int node;
int c;
};
int n, m, p;
int X, Y, A, B, C, D, Z;
vector<Edge> graph[MAXN];
int ancestors[18][MAXN];
int rmq[18][MAXN];
int depth[MAXN];
void ReadData() {
memset(rmq, 0x3f3f3f3f, sizeof rmq);
fin >> n >> m >> p;
for (int i = 2; i <= n; i++) {
int u, cost;
fin >> u >> cost;
ancestors[0][i] = u;
rmq[0][i] = cost;
graph[u].push_back({i, cost});
}
fin >> X >> Y >> A >> B >> C >> D;
}
void BuildAncestors(Edge node, int h) {
depth[node.node] = h;
for (int e = 1; e < 18; e++) {
ancestors[e][node.node] = ancestors[e - 1][ancestors[e - 1][node.node]];
rmq[e][node.node] = min(rmq[e - 1][node.node],
rmq[e - 1][ancestors[e - 1][node.node]]);
}
for (Edge newNode : graph[node.node]) {
BuildAncestors(newNode, h + 1);
}
}
int ComputeLCA(int a, int b) {
if (depth[a] < depth[b]) {
swap(a, b);
}
int ans = 0x3f3f3f3f;
int dif = depth[a] - depth[b];
for (int e = 0; e < 18; e++) {
if ((1 << e) & dif) {
ans = min(ans, rmq[e][a]);
a = ancestors[e][a];
}
}
if (a == b) {
return ans;
}
int savedA = a;
int savedB = b;
for (int e = 17; e >= 0; e--) {
if (ancestors[e][a] == ancestors[e][b]) {
continue;
}
a = ancestors[e][a];
b = ancestors[e][b];
}
int lca = ancestors[0][a];
a = savedA;
b = savedB;
dif = depth[a] - depth[lca];
for (int e = 0; e < 18; e++) {
if ((1 << e) & dif) {
ans = min(ans, rmq[e][a]);
a = ancestors[e][a];
}
}
dif = depth[b] - depth[lca];
for (int e = 0; e < 18; e++) {
if ((1 << e) & dif) {
ans = min(ans, rmq[e][b]);
b = ancestors[e][b];
}
}
return ans;
}
void Solve() {
for (int i = 0; i < m; i++) {
if (X == Y) {
Z = 0;
} else {
Z = ComputeLCA(X, Y);
}
X = (X * A + Y * B) % n + 1;
Y = (Y * C + Z * D) % n + 1;
if (m - i <= p) {
fout << Z << '\n';
}
}
}
int main() {
ReadData();
BuildAncestors({1, 0}, 1);
Solve();
return 0;
}