Pagini recente » Cod sursa (job #2313531) | Cod sursa (job #1872087) | Cod sursa (job #1755370) | Cod sursa (job #178157) | Cod sursa (job #2313535)
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz size()
using namespace std;
const int NR = 32001 ;
ifstream f("atac.in");
ofstream g("atac.out");
int level [ NR ] , euler [ NR * 2 ] , rmq [ 18 ][ 2 * NR ] , firstap [ NR * 2 ] , lg [ NR * 2 ] , cnt , n , m , p , Z , X , Y , A , B , C , D , TT [ NR ] , TTC [ NR ] , rmq_stramosi [ 16 ][ NR ] ;
vector < int > v [ NR ] ;
void intput ()
{
f >> n >> m >> p;
for ( int i = 2 ; i <= n ; ++ i )
{
int son , father = i , cost ;
f >> son >> cost ;
if ( son < father ) swap ( son , father ) ;
v [ father ].pb ( son ) ;
TT [ son ] = father ;
TTC [ son ] = cost ;
}
f >> X >> Y >> A >> B >> C >> D ;
}
int dfs ( int nod )
{
euler [ ++ cnt ] = nod ;
firstap [ nod ] = cnt ;
for ( size_t i = 0 ; i < v [ nod ].sz ; ++ i )
{
int vecin = v [ nod ][ i ] ;
level [ vecin ] = level [ nod ] + 1 ;
dfs ( vecin ) ;
euler [ ++ cnt ] = nod ;
}
}
void rmmq ()
{
for ( int i = 1 ; i <= cnt ; ++ i ) rmq [ 0 ][ i ] = euler [ i ] ;
for ( int i = 2 ; i <= cnt ; ++ i ) lg [ i ] = lg [ i >> 1 ] + 1 ;
for ( int i = 1 ; i <= lg [ cnt ] ; ++ i )
for ( int j = 1 ; j + ( 1 << i ) - 1 <= cnt ; ++ 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 ) ) ] ;
}
}
void idem_stramosi()
{
int rmqTT [ 16 ][ NR ] = { 0 } ;
for ( int j = 1 ; j <= n ; j ++ ) rmqTT [ 0 ][ j ] = TT [ j ] ;
for ( int i = 1 ; ( 1 << i ) <= n ; ++ i )
for ( int j = 1 ; j <= n ; j ++ )
rmqTT [ i ][ j ] = rmqTT [ i - 1 ][ rmqTT [ i - 1 ][ j ] ] ;
for (int i = 1 ; i <= n ; ++ i ) rmq_stramosi [ 0 ][ i ] = TTC [ i ] ;
for ( int i = 1 ; ( 1 << i ) <= n ; ++ i )
for ( int j = 1 ; j <= n ; ++ j )
{
rmq_stramosi [ i ][ j ] = rmq_stramosi [ i - 1 ][ j ] ;
int mij = rmqTT [ i - 1 ][ j ] ;
if ( rmq_stramosi [ i - 1 ][ mij ] < rmq_stramosi [ i ][ j ] && rmq_stramosi [ i - 1 ][ mij ] > 0 )
rmq_stramosi [ i ][ j ] = rmq_stramosi [ i - 1 ][ mij ] ;
}
}
int task ( int x , int y )
{
int st = firstap [ x ] , minim = ( 1 << 30 ) , dr = firstap [ y ] , lca , dist , log ;
if ( dr < st ) swap ( dr , st ) ;
dist = dr - st + 1 ;
log = lg [ dist ] ;
if ( level [ rmq [ log ][ st ] ] < level [ rmq [ log ][ dr - ( 1 << ( log ) ) + 1 ] ] )
lca = rmq [ log ][ st ] ;
else
lca = rmq [ log ][ dr - ( 1 << log ) + 1 ] ;
dist = lg [ level [ x ] - level [ lca ] ] ;
if ( rmq_stramosi [ dist ][ x ] && rmq_stramosi [ dist ][ x ] < minim ) minim = rmq_stramosi [ dist ][ x ] ;
if ( rmq_stramosi [ dist ][ x - ( 1 << dist ) + 1 ] && rmq_stramosi [ dist ][ x - (1 << dist ) + 1 ] < minim ) minim = rmq_stramosi [ dist ][ x - ( 1 << dist ) + 1 ] ;
dist = lg [ level [ y ] - level [ lca ] ] ;
if ( rmq_stramosi [ dist ][ y ] && rmq_stramosi [ dist ][ y ] < minim ) minim = rmq_stramosi [ dist ][ y ] ;
if ( rmq_stramosi [ dist ][ y - ( 1 << dist ) + 1 ] && rmq_stramosi [ dist ][ y - (1 << dist ) + 1 ] < minim ) minim = rmq_stramosi [ dist ][ y - ( 1 << dist ) + 1 ] ;
return minim ;
}
int solve_tasks ()
{
for ( int i = 1 ; i <= m ; ++ i )
{
if ( X != Y ) Z = task ( X , Y ) ;
else Z = 0 ;
if ( i >= m - p + 1 ) g << Z << "\n" ;
X = ( X * A + Y * B ) % n + 1 ;
Y = ( Y * C + Z * D ) % n + 1 ;
}
}
int main ()
{
intput() ;
dfs( 1 ) ;
rmmq() ;
idem_stramosi() ;
solve_tasks() ;
f.close() ;
g.close() ;
return 0 ;
}