Pagini recente » Cod sursa (job #403353) | Cod sursa (job #419220) | Cod sursa (job #725946) | Cod sursa (job #394589) | Cod sursa (job #1163346)
#include<fstream>
#include<vector>
#include<utility>
using namespace std;
#define max_n 33000
#define inf 200000
ifstream f("atac.in");
ofstream g("atac.out");
int n , m , q , A , B , C , D , X , Y , p;
int u , v , k , sol , nr , lca;
int Euler[25][4*max_n] , P[4*max_n];
int Nivel[max_n] , First[max_n];
pair<int , int> V[25][max_n];
vector< pair<int , int> > L[max_n];
void read(){
f>>n>>m>>q;
for( int i = 2 ; i <= n ; i++ ){
f>>u>>v;
L[u].push_back( make_pair( i , v ) );
L[i].push_back( make_pair( u , v ) );
}
f>>X>>Y>>A>>B>>C>>D;
}
void dfs( int nod , int niv , int tata ){
Euler[0][++k] = nod;
Nivel[nod] = niv;
if( First[nod] == 0 )
First[nod] = k;
for( unsigned int j = 0 ; j < L[nod].size() ; j++ ){
if( L[nod][j].first != tata ){
V[0][L[nod][j].first] = make_pair( nod , L[nod][j].second );
dfs( L[nod][j].first , niv + 1 , nod );
Euler[0][++k] = nod;
}
}
}
void rmq(){
for( int i = 2 ; i <= k ; i++ )
P[i] = 1 + P[i/2];
for( int i = 1 ; (1<<i) <= k ; i++ ){
for( int j = 1 ; j <= (k - (1<<i) + 1) ; j++ )
if( Nivel[ Euler[i-1][j] ] < Nivel[ Euler[i-1][j+(1<<(i-1))] ] )
Euler[i][j] = Euler[i-1][j];
else
Euler[i][j] = Euler[i-1][j+(1<<(i-1))];
}
for( int i = 1 ; (1<<i) <= n ; i++ ){
for( int j = 1 ; j <= n ; j++ ){
V[i][j] = V[i-1][V[i-1][j].first];
if( V[i][j].second > V[i-1][j].second )
V[i][j].second = V[i-1][j].second;
}
}
}
int minim( int a , int b ){
return a < b ? a : b;
}
void swap( int &x , int &y ){
int aux = x; x = y; y = aux;
}
int abs( int a ){
return a < 0 ? -a : a;
}
int Lca(){
int x = First[X] , y = First[Y];
if( x > y )
swap( x , y );
int p = P[ abs(y - x) + 1 ] , sol = Euler[p][x];
if( Nivel[sol] > Nivel[ Euler[p][ abs(y - (1<<p)) + 1] ] )
sol = Euler[p][ abs(y - (1<<p)) + 1];
return sol;
}
int find_sol(){
lca = Lca();
int x = X , y = Y , v_min = inf , nr;
nr = 0;
while( x != lca && nr < 30 ){
p = P[ Nivel[lca] - Nivel[x] ];
v_min = minim( v_min , V[p][x].second );
x = V[p][x].first;
nr++;
}
nr = 0;
while( y != lca && nr < 30 ){
p = P[ Nivel[lca] - Nivel[y] ];
v_min = minim( v_min , V[p][y].second );
y = V[p][y].first;
nr++;
}
return v_min;
}
void solve(){
for( int i = 1 ; i <= m ; i++ ){
sol = find_sol();
if( i >= (m - q + 1) ){
g<<X<<" "<<Y<<" ";
g<<sol<<"\n";
}
X = (X*A + Y*B) % n + 1;
Y = (Y*C + sol*D) % n + 1;
}
}
int main(){
read();
dfs( 1 , 1 , 0 );
rmq();
solve();
return 0;
}