Pagini recente » Cod sursa (job #1617572) | Cod sursa (job #2779833) | Cod sursa (job #1359812) | Cod sursa (job #1549682) | Cod sursa (job #1046532)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
const int nmax = 1 << 15;
int N, M, P;
int A, B, C, D;
int X, Y;
vector<int> G[nmax];
int T[16][nmax];
int cost[16][nmax];
int lg[nmax];
int lvl[nmax];
void readData() {
cin >> N >> M >> P;
for (int i = 2;i <= N;i++) {
cin >> T[0][i] >> cost[0][i];
G[i].push_back(T[0][i]);
G[T[0][i]].push_back(i);
}
cin >> X >> Y >> A >> B >> C >> D;
}
void df(int v,int fn) {
for (const int &w : G[v]) {
if (w != fn) {
lvl[w] = lvl[v] + 1;
df(w,v);
}
}
}
void compute() {
for (int i = 2;i <= N;i++) {
lg[i] = lg[i >> 1] + 1;
}
cost[0][0] = cost[0][1] = int(1e9);
for (int i = 1;(1 << i) <= N;i++) {
for (int j = 1;j <= N;j++) {
T[i][j] = T[i - 1][T[i - 1][j]];
int x = j;
for (int w = 0;w < i;w++) x = T[x][w];
cost[i][j] = min(cost[i - 1][x],cost[i - 1][T[i - 1][j]]);
}
}
}
inline int getLca(int x,int y) {
if (x == y)
return x;
if (lvl[x] > lvl[y]) {
while (lvl[x] > lvl[y]) {
x = T[lg[lvl[x] - lvl[y]]][x];
}
} else
if (lvl[y] > lvl[x]) {
while (lvl[y] > lvl[x]) {
y = T[lg[lvl[y] - lvl[x]]][y];
}
}
for(int l = lg[lvl[x]];l >= 0;l--) {
if (T[l][x] != T[l][y]) {
x = T[l][x];
y = T[l][y];
}
}
return T[0][x];
}
inline int query(int x,int y) {
if (x == y) {
return 0;
}
int lca = getLca(x,y);
int d = lvl[x] - lvl[lca];
int arr[] = {x,y};
int ret = int(1e9);
int l;
for (int i = 0;i < 2;i++) {
x = arr[i];
d = lvl[x] - lvl[lca];
while (d > 0) {
l = lg[d];
ret = min(ret,cost[l][x]);
x = T[l][x];
d -= (1 << l);
}
}
return ret;
}
int main()
{
readData();
compute();
df(1,0);
for (int i = 1;i <= M;i++) {
int Z = query(X,Y);
X = (X * A + Y * B) % N + 1;
Y = (Y * C + Z * D) % N + 1;
if (i >= M - P + 1) {
cout << Z << "\n";
}
}
return 0;
}