Pagini recente » Cod sursa (job #2599118) | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #2970562) | Cod sursa (job #2333323) | Cod sursa (job #2181110)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("atac.in");
ofstream out("atac.out");
const int NMax = 32005;
const int oo = 2000000000;
int N, M, P;
int A,B,C,D, X, Y, Z;
int lca;
int T[20][NMax], CM[20][NMax], Level[NMax], Log[NMax];
bool Use[NMax];
vector <pair<int, int>> G[NMax];
void Read()
{
in >> N >> M >> P;
for(int i = 2; i<=N;++i)
{
int x,y;
in >> x >> y;
G[x].push_back(make_pair(i,y));
G[i].push_back(make_pair(x,y));
}
in >> X >> Y >> A >> B >> C >> D;
}
void DFS(int Nod)
{
Use[Nod] = 1;
for(int i = 0; i < (int)G[Nod].size(); ++i)
{
int Vecin = G[Nod][i].first;
if(Use[Vecin])
{
T[0][Vecin] = Nod;
CM[0][Vecin] = G[Nod][i].second;
Level[Vecin] = Level[Nod] + 1;
DFS(Vecin);
}
}
}
void Precalculate()
{
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])
CM[i][j] = min(CM[i-1][j],CM[i-1][T[i-1][j]]);
}
}
for(int i = 2; i <= N ; ++i)
{
Log[i] = Log[i/2]+1;
}
}
int LCA(int x,int y)
{
if(Level[x]<Level[y])
swap(x,y);
while(Level[x] != Level[y])
{
int K = Log[Level[x]-Level[y]];
x = T[K][x];
}
if(x==y)
return x;
for(int i = Log[Level[x]]; i >= 0 ; i--)
{
if(T[i][x]!=T[i][y])
{
x = T[i][x];
y = T[i][y];
}
}
return T[0][x];
}
int Solve(int x, int y)
{
if(x == y)
return oo;
int d = Log[Level[x] - Level[y]]; //cand apelam y = lca => level mai mic
if(Level[T[d][x]] == Level[y])
return CM[d][x];
else
return min(CM[d][x], Solve(T[d][x],y));
}
int main()
{
Read();
Level[1] = 1;
DFS(1);
//Precalculate();
while(M--)
{
if(X==Y)
Z=0;
else
{
lca = LCA(X,Y);
Z = min(Solve(X,lca),Solve(Y,lca));
}
if(M < P)
out << Z << '\n';
//cout<< X << ' '<<Y<<'\n';
X=(X*A+Y*B)%N+1;
Y=(Y*C+Z*D)%N+1;
}
return 0;
}