Pagini recente » Cod sursa (job #1216439) | Cod sursa (job #1664375) | Rating Miu Catalin-Stefan (MiuCatalin) | Cod sursa (job #1254830) | Cod sursa (job #2098650)
#include<fstream>
#include<algorithm>
#include<deque>
#include<cstring>
#include<vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int N, M, P, Lca[32005][16], Rmq[32005][16], LOG;
int X, Y, A, B, C, D, Z, X1, Y1;
int Niv[32005], f[32005];
vector< pair<int,int> > v[32005];
deque<int> Ans;
void dfs( int nod, int nr ){
f[nod] = 1;
Niv[nod] = nr;
for( int i = 0; i < v[nod].size(); i++ ){
int vecin = v[nod][i].first;
if( f[vecin] == 0 ){
Lca[vecin][0] = nod;
Rmq[vecin][0] = v[nod][i].second;
dfs( vecin, nr + 1 );
}
}
return;
}
inline int LCA( int a, int b ){
if( Niv[a] > Niv[b] )
swap( a, b );
int D = Niv[b] - Niv[a];
int x = 0;
while( D != 0 ){
if( ( D & 1 ) == 1 )
b = Lca[b][x];
x++;
D >>= 1;
}
for( int i = LOG; i >= 0; i-- ){
if( Lca[a][i] != Lca[b][i] ){
a = Lca[a][i];
b = Lca[b][i];
}
}
if( a == b )
return a;
else
return Lca[a][0];
}
inline int solve1( int nod, int D ){
int r = 0x3f3f3f3f;
int x = 0;
while( D != 0 ){
if( ( D & 1 ) == 1 ){
r = min( r, Rmq[nod][x] );
nod = Lca[nod][x];
}
x++;
D >>= 1;
}
return r;
}
inline int solve( int X, int Y ){
if( X == Y )
return 0;
int nod = LCA( X, Y );
return min( solve1( X, Niv[X] - Niv[nod] ), solve1( Y, Niv[Y] - Niv[nod] ) );
}
int main(){
fin >> N >> M >> P;
for( int i = 1; i < N; i++ ){
int a, b;
fin >> a >> b;
v[i + 1].push_back( make_pair( a, b ) );
v[a].push_back( make_pair( i + 1, b ) );
}
memset( Rmq, 0x3f3f3f3f, sizeof(Rmq) );
dfs( 1, 1 );
for( int k = 1; (1<<k) <= N; k++, LOG = k )
for( int i = 1; i <= N; i++ )
Lca[i][k] = Lca[ Lca[i][k - 1] ][k - 1];
for( int k = 1; (1<<k) <= N; k++ )
for( int i = 1; i <= N; i++ )
Rmq[i][k] = min( Rmq[i][k - 1], Rmq[ Lca[i][k - 1] ][k - 1] );
fin >> X >> Y >> A >> B >> C >> D;
for( int i = 1; i <= M; i++ ){
Z = solve( X, Y );
Ans.push_back( Z );
if( Ans.size() == P + 1 )
Ans.pop_front();
X1 = ( X * A + Y * B ) % ( N + 1 );
Y1 = ( Y * C + Z * D ) % ( N + 1 );
X = X1;
Y = Y1;
}
for( int i = 0; i < Ans.size(); i++ )
fout << Ans[i] << "\n";
return 0;
}