Pagini recente » Cod sursa (job #441047) | Cod sursa (job #800001) | Cod sursa (job #1537051) | Cod sursa (job #2165480) | Cod sursa (job #1211016)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 32e3 + 1;
const int Mmax = 5e5 + 1;
const int LgMax = 15 + 1;
vector < pair<int,int> > G[Nmax];
int rmq[LgMax][Nmax];
int father[Nmax], level[Nmax];
int N, M, P;
int X, Y, Z;
int A, B, C, D;
void DFS( int node )
{
for ( auto x: G[node] )
{
if ( father[x.first] == 0 )
{
father[x.first] = node;
rmq[0][x.first] = x.second;
level[x.first] = level[node] + 1;
DFS( x.first );
}
}
}
void build_rmq()
{
for ( int i = 1; ( 1 << i ) <= N; ++i )
for ( int j = 1; j + ( 1 << i ) - 1 <= N; ++j )
{
int p = 1 << ( i - 1 );
rmq[i][j] = min( rmq[i - 1][j], rmq[i - 1][j + p] );
}
}
int lca( int x, int y )
{
while ( x != y )
{
if ( level[x] < level[y] )
y = father[y];
else
x = father[x];
}
return x;
}
int get_min( int x, int y )
{
if ( level[x] < level[y] )
swap( x, y );
if ( x == y )
return 0;
int L = lca( x, y );
int sol = 1e9;
while ( x != L )
{
sol = min( sol, rmq[0][x] );
x = father[x];
}
while ( y != L )
{
sol = min( sol, rmq[0][y] );
y = father[y];
}
return sol;
}
int main()
{
ifstream in("atac.in");
ofstream out("atac.out");
in.sync_with_stdio( false );
in >> N >> M >> P;
for ( int i = 2, a, c; i <= N; ++i )
{
in >> a >> c;
G[a].push_back( make_pair( i, c ) );
G[i].push_back( make_pair( a, c ) );
}
in >> X >> Y >> A >> B >> C >> D;
father[1] = 1;
rmq[0][1] = 1e9;
level[1] = 0;
DFS( 1 );
build_rmq();
for ( int i = 1; i <= M; ++i )
{
Z = get_min( X, Y );
if ( i >= P )
out << Z << "\n";
X = ( X * A + Y * B ) % N + 1;
Y = ( Y * C + Z * D ) % N + 1;
}
return 0;
}