Pagini recente » Cod sursa (job #2694847) | Cod sursa (job #1862237) | Cod sursa (job #2729217) | Cod sursa (job #1638216) | Cod sursa (job #2313531)
#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 ] ; // hai ca nu-i greu
int euler [ NR * 2 ] ; // parcurgerea euler
int rmq [ 18 ][ 2 * NR ] ; // rmq [ i ][ j ] - nodul de nivel minim din lantul [ i - j ]
int firstap [ NR * 2 ] ; // prima aparitie in euler
int lg [ NR * 2 ] ; // ??
int cnt , n , m , p , Z , X , Y , A , B , C , D ;
int TT [ NR ] ; // TT [ i ] - tatal lui i
int TTC [ NR ] ; // TTC [ i ] - costul muchiei [ i - TT [ i ] ]
int rmq_stramosi [ 16 ][ NR ] ; // rmq_stramosi [ i ][ j ] - costul minim al unei muchii din lantul [ j - al ( 2 ^ i - lea parinte al lui j ) ]
// rmqTT [ i ][ j ] - al 2 ^ i - lea strabun al lui j
vector < pair < int , int > > v [ NR ] ; // V [ i ] - retine fii nodului i
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 ( mp ( son , cost ) ) ;
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 ].first ;
int cost = v [ nod ][ i ].second ;
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 ) <= cnt + 1 ; ++ 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 ] ;
if ( rmq_stramosi [ i - 1 ][ rmqTT [ i - 1 ][ j ] ] < rmq_stramosi [ i ][ j ] && rmq_stramosi [ i - 1 ][ rmqTT [ i - 1 ][ j ] ] > 0 )
rmq_stramosi [ i ][ j ] = rmq_stramosi [ i - 1 ][ rmqTT [ i - 1 ][ j ] ] ;
}
}
int task ( int x , int y )
{
int st = firstap [ x ] , minim = ( 1 << 30 ) , dr = firstap [ y ] , lca , dist;
if ( dr < st ) swap ( dr , st ) ;
dist = dr - st + 1 ;
if ( level [ rmq [ lg [ dist ] ][ st ] ] < level [ rmq [ lg [ dist ] ][ dr - ( 1 << ( lg [ dist ] ) ) + 1 ] ] )
lca = rmq [ lg [ dist ] ][ st ] ;
else
lca = rmq [ lg [ dist ] ][ dr - ( 1 << ( lg [ dist ] ) ) + 1 ] ;
dist = lg [ level [ x ] - level [ lca ] + 1 ] + 1 ;
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 ] + 1 ] + 1 ;
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 ] ;
return minim ;
}
int solve_tasks ()
{
for ( int i = 1 ; i <= m ; ++ i )
{
if ( X != Y ) Z = task ( X , Y ) ;
else Z = 0 ;
if ( i >= p ) 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 ;
}