Pagini recente » Cod sursa (job #1665476) | Cod sursa (job #1423132) | Cod sursa (job #2229611) | Cod sursa (job #1419469) | Cod sursa (job #931169)
Cod sursa(job #931169)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in ("atac.in");
ofstream out ("atac.out");
const int N = 32001;
int n,m,p,X,Y,A,B,C,D,T[16][N],COST[16][N],lvl[N],log[N];
vector<pair<int,int> > G[N];
void READ ()
{
in>>n>>m>>p;
for( int x,c,i=2 ; i <= n ; ++i )
{
in>>x>>c;
G[i].push_back(make_pair(x,c));
G[x].push_back(make_pair(i,c));
}
in>>X>>Y>>A>>B>>C>>D;
}
void DFS (int nod)
{
for( vector<pair<int,int> >::iterator it=G[nod].begin() ; it < G[nod].end() ; ++it )
if( T[0][nod] != it->first )
{
T[0][it->first]=nod;
COST[0][it->first]=it->second;
lvl[it->first]=lvl[nod]+1;
DFS (it->first);
}
}
int LCA ( int nod1 , int nod2 )
{
for( ; lvl[nod1] < lvl[nod2] ; nod2=T[log[lvl[nod2]-lvl[nod1]]][nod2] );
for( ; lvl[nod2] < lvl[nod1] ; nod1=T[log[lvl[nod1]-lvl[nod2]]][nod1] );
if( nod1 == nod2)
return nod1;
for( int i=log[lvl[nod1]] ; i>=0 ; --i )
if( T[i][nod1] != T[i][nod2] )
{
nod1=T[i][nod1];
nod2=T[i][nod2];
}
return T[0][nod1];
}
int GET ( int nod , int Ds )
{
int mn=1<<30;
for( ; Ds ; Ds-=(1<<log[Ds]) )
{
mn=min(mn,COST[log[Ds]][nod]);
nod=T[log[Ds]][nod];
}
return mn;
}
int QUERY ( int nod1 , int nod2 )
{
if( nod1 == nod2 )
return 0;
int F=LCA(nod1,nod2);
int mnd1=GET( nod1 , lvl[nod1]-lvl[F] );
int mnd2=GET( nod2 , lvl[nod2]-lvl[F] );
return min(mnd1,mnd2);
}
void SOLVE ()
{
for( int i=2 ; i <= n ; ++i )
log[i]=log[i>>1]+1;
for( int i=1 ; i <= log[n] ; ++i )
for( int j=1 ; j <= n ; ++j )
{
T[i][j]=T[i-1][T[i-1][j]];
COST[i][j]=min(COST[i-1][j],COST[i-1][T[i-1][j]]);
}
for( ; m > p ; --m )
{
int Z=QUERY(X,Y);
X=(A*X+Y*B)%n+1;
Y=(Y*C+Z*D)%n+1;
}
}
void PRINT ()
{
for( ; m ; --m )
{
int SOL=QUERY(X,Y);
X=(A*X+B*Y)%n+1;
Y=(C*Y+D*SOL)%n+1;
out<<SOL<<'\n';
}
}
int main ()
{
READ ();
DFS (1);
SOLVE ();
PRINT ();
return 0;
}