Pagini recente » Borderou de evaluare (job #808214) | Cod sursa (job #399535) | Cod sursa (job #255276) | Cod sursa (job #748479) | Cod sursa (job #2605413)
#include <bits/stdc++.h>
#define ULL unsigned long long
#define Inf 1000000007
using namespace std;
ifstream in("atac.in");
ofstream out("atac.out");
int n,Q,P;
int vf[64001],urm[64001],cost[64001],last[32001],nr;
int euler[64001],nivEu[64001],pozitie[32001],Nivel[32001],t;
int rmq[16][64001];
int stram[15][32001],minim[15][32001];
int x,y,z;
ULL A,B,C,D;
void adauga(int nod,int vec,int ct)
{
vf[++nr]=vec;
urm[nr]=last[nod];
last[nod]=nr;
cost[nr]=ct;
}
void citire()
{
in>>n>>Q>>P;
for(int i=2,j,ct;i<=n;i++)
{
in>>j>>ct;
adauga(i,j,ct);
adauga(j,i,ct);
}
in>>x>>y>>A>>B>>C>>D;
}
void dfs(int nod=1,int from=0,int nivel=1)
{
euler[++t]=nod;
nivEu[t]=nivel;
pozitie[nod]=t;
stram[0][nod]=from;
Nivel[nod] = nivel;
for(int k=last[nod];k;k=urm[k])
if(vf[k]!=from)
{
dfs(vf[k],nod,nivel+1);
euler[++t]=nod;
nivEu[t]=nivel;
minim[0][vf[k]]=cost[k];
}
}
void rmqBuild()
{
int maxim = 2*n-1;
int rMax = log2(maxim);
for(int i=1; i<=maxim; i++)
rmq[0][i] = i;
for(int r=1,l=1; r<=rMax; r++,l*=2)
for(int i=1;i<= maxim-2*l+1;i++)
if( nivEu[ rmq[r-1][i] ] < nivEu[ rmq[r-1][i+l] ] )
rmq[r][i]=rmq[r-1][i];
else
rmq[r][i]=rmq[r-1][i+l];
}
void stramosBuild()
{
minim[0][1]=Inf;
int rMax=log2(n);
for(int r=1;r<=rMax;r++)
for(int i=1;i<=n;i++)
{
stram[r][i] = stram[r-1][ stram[r-1][i] ];
minim[r][i] = min( minim[r-1][i], minim[r-1][ stram[r-1][i] ] );
}
}
int lca(int x,int y)
{
int st = pozitie[x];
int dr = pozitie[y];
if(st>dr)
swap(st,dr);
int r = log2( dr-st+1 );
if( nivEu[ rmq[r][st] ] < nivEu[ rmq[r][dr-(1<<r)+1] ] )
return euler[ rmq[r][st] ];
else
return euler[ rmq[r][dr-(1<<r)+1] ];
}
int distMin(int nod,int dest)
{
int Minim = Inf;
int Dist = Nivel[nod] - Nivel[dest];
for( int j=0; (1<<j)<=Dist; j++)
if( (1<<j)&Dist )
{
Minim = min(Minim, minim[j][nod] );
nod = stram[j][nod];
}
return Minim;
}
int main()
{
citire();
dfs();
rmqBuild();
stramosBuild();
for( int k=1;k<=Q;k++ )
{
int p = lca(x,y);
if(x!=y)
z = min( distMin(x,p) , distMin(y,p) );
else
z = 0;
x = ( A*x + B*y ) % n +1;
y = ( C*y + D*z ) % n +1;
if(k>Q-P)
out<<z<<'\n';
}
return 0;
}