Pagini recente » Cod sursa (job #2716310) | Cod sursa (job #2518220) | Cod sursa (job #500870) | Cod sursa (job #270366) | Cod sursa (job #2346696)
#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, Lev[NMax + 5], Dist[NMax + 5], T[20][NMax + 5], Z, DT[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]];
}
}
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[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];
}
void Bomb(int Nod, int F)
{
while(Nod != F)
{
Z = min(Z, DT[Nod]);
Nod = T[0][Nod];
}
}
void SolveP()
{
for(int i = 1; i <= M; i++)
{
int Nod = LCA(X, Y); Z = oo;
if(X == Y) Z = 0;
Bomb(X, Nod);
Bomb(Y, Nod);
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;
}