Pagini recente » Cod sursa (job #194713) | Cod sursa (job #408780) | Cod sursa (job #1520458) | Cod sursa (job #626979) | Cod sursa (job #425061)
Cod sursa(job #425061)
#include <stdio.h>
#include <vector>
#define IN "atac.in"
#define OUT "atac.out"
#define Lg 32010
#define L 20
#define INF 0x3f3f3f3f
using namespace std;
struct lol
{
int Dir,B;
}l;
int rmq[L][Lg*4];
int X,Y,A,B,C,D,Z,m,p,n;
vector <lol> V[Lg];
int Grad[Lg*4];
int Niv[Lg*4];
int Euler[Lg*4],nr;
int ap[Lg*4];
int viz[Lg];
int Bombe[Lg*4];
int put[Lg*4];
int T[Lg];
int Co[Lg];
void citire()
{
scanf ("%d %d %d",&n,&m,&p);
for (int i=2;i<=n;i++)
{
scanf ("%d %d",&l.Dir, &l.B);
Grad[i]++;
Grad[l.Dir]++;
V[i].push_back(l);
X=l.Dir;
l.Dir=i;
V[X].push_back(l);
}
scanf ("%d %d %d %d %d %d",&X,&Y,&A,&B,&C,&D);
}
void df(int nod)
{
viz[nod]=1;
for (int i=0;i<Grad[nod];i++)
if (!viz[V[nod][i].Dir])
{
Euler[nr++]=V[nod][i].Dir;
T[V[nod][i].Dir]=nod;
Co[V[nod][i].Dir]=V[nod][i].B;
if (ap[V[nod][i].Dir]==0)
ap[V[nod][i].Dir]=nr-1;
Niv[V[nod][i].Dir]=Niv[nod]+1;
df(V[nod][i].Dir);
Euler[nr++]=nod;
}
}
int mi(int a,int b)
{
return Niv[a]<Niv[b]?a:b;
}
void RMQ()
{
int n=nr;
for (int i=2;i<=n;i++)
{
put[i]=put[i>>1]+1;
rmq[0][i]=Euler[i];
}
rmq[0][1]=Euler[1];
for (int i=1; i<=put[n];i++)
for (int j=1;j<=n-(1<<(i))+1;j++)
rmq[i][j]=mi(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
int mini(int a,int b)
{
return a<b?a:b;
}
void solve()
{
int X1,Y1,P,Nod;
Euler[1]=1;
ap[1]=1;
Niv[1]=1;
nr=2;
df(1);
RMQ();
for (int i=1;i<=m;i++)
{
X1=X;
Y1=Y;
Z=0;
if (X1!=Y1)
{
if (ap[X1]>ap[Y1])
{
int aux=X1;
X1=Y1;
Y1=aux;
}
P=put[ap[Y1]-ap[X1]+1];
Nod=mi(rmq[P][ap[X1]], rmq[P][ap[Y1]-(1<<P)+1]);
Z=0x3f3f3f3f;
while (X1!=Nod)
{
Z=mini(Z,Co[X1]);
X1=T[X1];
}
while (Y1!=Nod)
{
Z=mini(Z,Co[Y1]);
Y1=T[Y1];
}
}
if (i+P>=m)
printf("%d\n",Z);
X=(X*A+Y*B)%n+1;
Y=(Y*C+Z*D)%n+1;
}
}
int main ()
{
freopen (IN ,"r", stdin);
freopen (OUT ,"w", stdout);
citire();
solve();
return 0;
}