Pagini recente » Cod sursa (job #943738) | Cod sursa (job #1145594) | Cod sursa (job #2684689) | Cod sursa (job #282153) | Cod sursa (job #2314591)
/*
Code by
ANDREI ARHIRE
Galati, ROMANIA
*/
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz size()
using namespace std;
const int NR = 32001 ;
const int oo = ( 1 << 30 ) ;
ifstream f ("atac.in") ;
ofstream g ("atac.out") ;
vector < pair < int , int > > v [ NR ] ;
int cnt , level [ NR ] , euler [ 2 * NR ] , rmq [ 20 ][ 2 * NR ] , rmq_father [ 16 ][ NR ] , rmq_edge [ 16 ][ NR ] , Father [ NR ] , Father_edge [ NR ] , firstap [ 2 * NR ] , lg [ 2 * NR ] , X , Y , Z , A , B , C , D , m , n , p ;
void input ()
{
f >> n >> m >> p ;
for ( int i = 2 ; i <= n ; ++ i )
{
int father = i , son , cost ;
f >> son >> cost ;
if ( father > son ) swap ( father , son ) ;
v[ father ].pb ( mp ( son , cost ) ) ;
v [ son ].pb ( mp ( father , cost ) ) ;
}
f >> X >> Y >> A >> B >> C >> D ;
}
void dfs ( int nod , int father , int cost )
{
level [ nod ] = level [ euler [ cnt ] ] + 1 ;
Father [ nod ] = father ;
Father_edge [ nod ] = cost ;
euler [ ++ cnt ] = nod ;
firstap [ nod ] = cnt ;
for ( size_t i = 0 ; i < v[ nod ].sz ; ++ i )
{
if ( !firstap [ v [ nod ][ i ].first ] )
{
dfs ( v [ nod ][ i ].first , nod , v [ nod ][ i ].second ) ;
euler [ ++ cnt ] = nod ;
}
}
}
void rmq_fun ( )
{
for ( int i = 2 ; i <= cnt ; ++ i ) lg [ i ] = lg [ i >> 1 ] + 1 ;
for ( int i = 1 ; i <= cnt ; ++ i ) rmq [ 0 ][ i ] = euler [ i ] ;
for ( int i = 1 ; ( 1 << i ) <= cnt ; ++ i )
for ( int j = 1 ; j + ( 1 << i ) - 1 <= cnt ; ++ j )
{
rmq [ i ][ j ] = rmq [ i - 1 ][ j ] ;
if ( level [ rmq [ i - 1 ] [ j ] ] > level [ rmq [ i - 1 ][ j + ( 1 << ( i - 1 ) ) ] ] )
rmq [ i ][ j ] = rmq [ i - 1 ][ j + ( 1 << ( i - 1 ) ) ] ;
}
}
int lca_fun ( int i , int j )
{
int st = firstap [ i ] , dr = firstap [ j ] ;
if ( dr < st ) swap ( dr , st ) ;
int log = lg [ dr - st + 1 ] ;
if ( level [ rmq [ log ][ st ] ] < level [ rmq [ log ][ dr - ( 1 << log ) + 1 ] ] )
return rmq [ log ][ st ] ;
return rmq [ log ][ dr - ( 1 << log ) + 1 ] ;
}
int rmq_father__rmq_edge_fun ( )
{
for ( int i = 1 ; i <= n ; ++ i ) rmq_father [ 0 ][ i ] = Father [ i ] ;
for ( int i = 1 ; ( 1 << i ) <= n ; ++ i )
for ( int j = 1 ; j <= n ; ++ j ) rmq_father [ i ][ j ] = rmq_father [ i - 1 ][ rmq_father [ i - 1 ][ j ] ] ;
for ( int i = 1 ; i <= n ; ++ i ) rmq_edge [ 0 ][ i ] = Father_edge [ i ] ;
for ( int i = 1 ; ( 1 << i ) <= n ; ++ i )
for ( int j = 1 ; j <= n ; ++ j ) rmq_edge [ i ][ j ] = min ( rmq_edge [ i - 1 ][ j ] , rmq_edge [ i - 1 ][ rmq_father [ i - 1 ][ j ] ] ) ;
}
int min_edge ( int nod , int lca )
{
if ( lca == nod ) return oo ;
int log = lg [ level [ nod ] - level [ lca ] ] ;
int ans = rmq_edge [ log ][ nod ] ;
int dist = level [ nod ] - level [ lca ] - ( 1 << log ) ;
int k = lg [ n ] ;
while ( k -- ) if ( ( 1 << k ) & dist ) nod = rmq_father[ k ][ nod ] ;
return min ( ans , rmq_edge[ log ][ nod ] ) ;
}
int task ( int x , int y )
{
int lca = lca_fun( x , y ) ;
return min ( min_edge( x , lca ) , min_edge( y , lca ) ) ;
}
void solve()
{
for ( int i = 1 ; i <= m ; ++ i )
{
if ( X == Y ) Z = 0 ;
else Z = task( X , Y ) ;
if ( i >= m - p + 1 ) g << Z << "\n" ;
X = ( X * A + Y * B ) % n + 1 ;
Y = ( Y * C + Z * D ) % n + 1 ;
}
}
int main ()
{
input() ;
dfs( 1, 0 , 1 << 30 ) ;
rmq_fun() ;
rmq_father__rmq_edge_fun() ;
solve() ;
}