Pagini recente » Cod sursa (job #709629) | Cod sursa (job #2902850) | Cod sursa (job #151302) | Cod sursa (job #2309763) | Cod sursa (job #1951461)
#include <iostream>
#include <fstream>
#include <vector>
#define maxn 32000
#define mmax 500000
using namespace std;
int n,m,p,x,y,a,b,c,d,x1,y1;
int P[maxn+5][15];
int C[maxn+5][15];
int v[maxn+5][2];
int L[maxn+5];
int Log[32005];
int LCA(int p, int q)
{
if(L[p]<L[q])
{
int tmp=p;
p=q;
q=tmp;
}
int log;
for(log=1;1<<log <= L[p];log++);
log--;
for(int i=log;i>=0;i--)
if(L[p]- (1<<i)>= L[q])
p=P[p][i];
if(p==q) return p;
for(int i=log;i>=0;i--)
if(P[p][i]!=-1 && P[p][i]!=P[q][i])
p=P[p][i],q=P[q][i];
return v[p][0];
}
int RMQ(int p, int q)
{ if(p==q) return 0;
int up=LCA(p,q),cmin=100005,a;
while(p!=up)
{
a=Log[ L[p]-L[up] ];
cmin=min(cmin,C[p][a]);
p=P[p][a];
}
while(q!=up)
{
a=Log[ L[q]-L[up] ];
cmin=min(cmin,C[q][a]);
q=P[q][a];
}
return cmin;
}
int main()
{
ifstream fin("atac.in");
ofstream fout("atac.out");
fin>>n>>m>>p;
L[1]=0;
for(int i=2;i<=n;i++)
Log[i]=Log[i/2]+1;
for(int i=2;i<=n;i++)
{
int x,z;
fin>>x>>z;
v[i][0]=x;
v[i][1]=z;
L[i]=L[x]+1;
}
v[1][0]=1;
v[1][1]=0;
fin>>x>>y>>a>>b>>c>>d;
for(int i=1;i<=n;i++)
for(int j=0;1<<j<n;j++)
P[i][j]=-1;
for(int i=1;i<=n;i++)
{P[i][0]=v[i][0];
C[i][0]=v[i][1];
}
for(int j=1;(1<<j) <n;j++)
for(int i=0;i<=n;i++)
{if(P[i][j-1]!=-1)
{P[i][j]=P[ P[i][j-1] ][ j-1 ];
C[i][j]=min(C[ P[i][j-1] ][j-1], C[i][j-1]);
}
}
while(m>p)
{
y1=(y*c+RMQ(x,y)*d)%n+1;
x1=(x*a+y*b)%n+1;
x=x1,y=y1;
m--;
}
for(int i=1;i<=p;i++)
{
int z=RMQ(x,y);
fout<<z<<'\n';
y1=(y*c+z*d)%n+1;
x1=(x*a+y*b)%n+1;
x=x1,y=y1;
}
fin.close();
fout.close();
return 0;
}