Pagini recente » Cod sursa (job #2457800) | Cod sursa (job #2731343) | Cod sursa (job #2476675) | Cod sursa (job #1546552) | Cod sursa (job #2346706)
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int NMax = 32000, oo = 1e9;
int N, M, P, X, Y, A, B, C, D, Z, Lev[NMax + 5], T[20][NMax + 5], DT[20][NMax + 5];
struct str{int n, c;};
vector <str> G[NMax + 5];
void Read()
{
fin >> N >> M >> P;
for(int i = 2, x, c; i <= N; i++)
{
fin >> x >> c;
G[i].push_back({x, c});
G[x].push_back({i, c});
}
fin >> X >> Y >> A >> B >> C >> D;
fin.close();
}
void Precalc()
{
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]];
if(T[i][j])
DT[i][j] = min(DT[i - 1][j], DT[i - 1][T[i - 1][j]]);
}
}
}
void DFS(int Nod, int Tata)
{
Lev[Nod] = Lev[Tata] + 1, T[0][Nod] = Tata;
for(auto Vecin : G[Nod])
{
if(Vecin.n == Tata) continue;
DT[0][Vecin.n] = Vecin.c;
DFS(Vecin.n, Nod);
}
}
int Stramos(int Nod, int P)
{
int k = 0;
while(P) {
if(P & 1) Nod = T[k][Nod];
P >>= 1, k++;
}
return Nod;
}
int LCA(int x, int y)
{
if(Lev[x] < Lev[y]) swap(x, y);
if(Lev[x] != Lev[y])
x = Stramos(x, Lev[x] - Lev[y]);
if(x == y) return x;
for(int i = log2(Lev[x]); i >= 0; i--)
{
if(T[i][x] != T[i][y])
x = T[i][x], y = T[i][y];
}
return T[0][x];
}
int Bomb(int Nod, int F)
{
int k = 0, Sol = oo, P = Lev[Nod] - Lev[F];
while(P)
{
if(P & 1) Sol = min(Sol, DT[k][Nod]), Nod = T[k][Nod];
P >>= 1, k++;
}
return Sol;
}
void SolveP()
{
for(int i = 1; i <= M; i++)
{
int Nod = LCA(X, Y);
Z = min(Bomb(X, Nod), Bomb(Y, Nod));
if(X == Y) Z = 0;
if(M - i + 1 <= P)
fout << Z << '\n';
X = (X * A + Y * B) % N + 1;
Y = (Y * C + Z * D) % N + 1;
}
fout.close();
}
int main()
{
Read();
DFS(1, 0);
Precalc();
SolveP();
return 0;
}