Pagini recente » Cod sursa (job #1084554) | Cod sursa (job #941253) | Cod sursa (job #1585709) | Cod sursa (job #1215334) | Cod sursa (job #1537619)
#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>
#define FILEIN "atac.in"
#define FILEOUT "atac.out"
using namespace std;
const int NMAX = 32005; // log = 15
const int INF = 0x3f3f3f3f;
int cnt = 0;
int n, p, m;
int x, y, a, b, c, d;
vector<pair<int, int> > A[NMAX];
int P[NMAX][15];
int M[NMAX][15];
int D[NMAX];
int Uz[NMAX];
int First[NMAX];
int Last[NMAX];
int Euler[NMAX * 2 + 1];
int RMQ[NMAX * 2 + 1][15];
int LG[NMAX * 2 + 1];
void dfs(int x) {
Uz[x] = 1;
First[x] = ++cnt;
Last[x] = cnt;
Euler[cnt] = x;
for (int i = 0; i < A[x].size(); i++) {
int y = A[x][i].first;
if (Uz[y])
continue;
int c = A[x][i].second;
P[y][0] = x;
M[y][0] = c;
for (int j = 1; ; j++) {
P[y][j] = P[P[y][j-1]][j-1];
if (!P[y][j])
break;
M[y][j] = min(M[y][j], M[P[y][j-1]][j-1]);
}
D[y] = D[x] + 1;
Uz[y] = 1;
dfs(y);
Last[x] = ++cnt;
Euler[cnt] = x;
}
}
int lca(int x, int y) {
int a = min(First[x], First[y]);
int b = max(First[x], First[y]);
int len = LG[b - a + 1];
if (D[RMQ[a][len]] < D[RMQ[b - (1 << len) + 1][len]])
return RMQ[a][len];
return RMQ[b - (1 << len) + 1][len];
}
void process() {
D[1] = 1;
memset(M, INF, sizeof(M));
dfs(1);
for (int i = 2; i <= NMAX * 2; i++) {
LG[i] = LG[i/2] + 1;
}
for (int i = 1; i <= n * 2; i++) {
RMQ[i][0] = Euler[i];
}
for (int j = 1; j < 15; j++) {
for (int i = 1; i + (1 << (j-1)) <= n * 2; i++) {
if (D[RMQ[i][j - 1]] < D[RMQ[i + (1 << (j-1))][j - 1]])
RMQ[i][j] = RMQ[i][j-1];
else
RMQ[i][j] = RMQ[i + (1 << (j-1))][j-1];
}
}
}
int tree_min(int x, int ancestor) {
int diff = D[x] - D[ancestor];
int ans = INF;
while (diff) {
ans = min(ans, M[x][LG[diff]]);
diff -= diff & (-diff);
}
if (ans == INF)
return 0;
return ans;
}
int query(int x, int y) {
int t = lca(x, y);
if (x == y)
return 0;
if (t == x)
return tree_min(y, t);
if (t == y)
return tree_min(x, t);
return min(tree_min(x, t), tree_min(y, t));
}
int main() {
freopen(FILEIN, "r", stdin);
freopen(FILEOUT, "w", stdout);
cin >> n >> m >> p;
for (int i = 2; i <= n; i++) {
cin >> x >> c;
A[x].push_back(make_pair(i, c));
A[i].push_back(make_pair(x, c));
}
process();
cin >> x >> y >> a >> b >> c >> d;
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;
}