Pagini recente » Cod sursa (job #1138847) | Cod sursa (job #2983852) | Cod sursa (job #2738772) | Cod sursa (job #2081009) | Cod sursa (job #734593)
Cod sursa(job #734593)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define maxN 32010
#define maxK 17
#define inf (1 << 30)
#define PB push_back
#define MKP make_pair
#define f first
#define s second
int N, Level[maxN], Ap[maxN];
int Euler[maxN << 1], rmq[maxK << 1][maxN << 1];
int Father[maxK][maxN], MinE[maxK][maxN];
int Lg[maxN << 1];
vector <pair <int, int> > List[maxN];
void DFS (int nod)
{
Euler[++ Euler[0]] = nod;
Ap[nod] = Euler[0];
for (int i = 0; i < List[nod].size(); ++ i)
{
int nod2 = List[nod][i].f, cost2 = List[nod][i].s;
Level[nod2] = Level[nod] + 1;
Father[0][nod2] = nod;
MinE[0][nod2] = cost2;
DFS (nod2);
Euler[++ Euler[0]] = nod;
}
}
void RMQ ()
{
for (int i = 1; (1 << i) <= N; ++ i)
for (int j = 1; j <= N; ++ j)
{
Father[i][j] = Father[i - 1][Father[i - 1][j]];
MinE[i][j] = min (MinE[i - 1][MinE[i - 1][j]], MinE[i - 1][j]);
}
for (int i = 1; i <= Euler[0]; ++ i) rmq[0][i] = Euler[i];
for (int i = 1; (1 << i) <= Euler[0]; ++ i)
for (int j = 1; j <= Euler[0] - (1 << i) + 1; ++ j)
if (Level[rmq[i - 1][j]] < Level[rmq[i - 1][j + (1 << (i - 1))]]) rmq[i][j] = rmq[i - 1][j];
else rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
}
inline int LCA (int X, int Y)
{
if (X > Y) swap (X, Y);
int nrE = Y - X + 1;
int K = Lg[nrE];
if (Level[rmq[K][X]] < Level[rmq[K][Y - (1 << K) + 1]]) return rmq[K][X];
else return rmq[K][Y - (1 << K) + 1];
}
inline int Get_MinE (int X, int Y)
{
if (X == Y) return inf;
int K = Lg[Level[X] - Level[Y]];
return min (MinE[K][X], Get_MinE(Father[K][X], Y));
}
int main()
{
freopen ("atac.in", "r", stdin);
freopen ("atac.out", "w", stdout);
int M, P;
scanf ("%d %d %d", &N, &M, &P);
for (int i = 2, U, V; i <= N; ++ i)
{
scanf ("%d %d", &U, &V);
List[U].PB (MKP (i, V));
}
DFS (1);
RMQ ();
for (int i = 2; i <= Euler[0]; ++ i) Lg[i] = Lg[i / 2] + 1;
int X, Y, A, B, C, D;
scanf ("%d %d %d %d %d %d", &X, &Y, &A, &B, &C, &D);
for (int i = 1; i <= M; ++ i)
{
int Z = LCA (Ap[X], Ap[Y]);
int ans = min (Get_MinE (X, Z), Get_MinE (Y, Z));
if (ans == inf) ans = 0;
if (i > M - P) printf ("%d\n", ans);
X = (X * A + Y * B) % N + 1;
Y = (Y * C + ans * D) % N + 1;
}
return 0;
}