Pagini recente » Cod sursa (job #2638643) | Cod sursa (job #1111159) | Cod sursa (job #83756) | Cod sursa (job #2516712) | Cod sursa (job #2836363)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int n,m,p,P;
int a,b,c,d,x,y;
vector<pair<int,int> >h[33000];
int sol[500005],t;
int niv[33000],viz[33000],poz[65000],lg[65000],e[66000];
int rmq[20][65000];
void Citire()
{
int i;
fin>>n>>m>>P;
for(i=2;i<=n;i++)
{
fin>>x>>y;
h[i].push_back({x,y});
h[x].push_back({i,y});
}
fin>>x>>y>>a>>b>>c>>d;
}
void DFS(int x)
{
viz[x]=1;
for(auto i:h[x])
if(!viz[i.first])
{
niv[i.first]=niv[x]+1;
DFS(i.first);
}
}
void SkemaTovarasuluiEuler(int k)
{
e[++p]=k;
if(poz[k]==0)
poz[k]=p;
for(auto i:h[k])
if(niv[i.first]==niv[k]+1)
{
SkemaTovarasuluiEuler(i.first);
e[++p]=k;
}
}
void MakeRMQ()
{
int i,j;
lg[1]=0;
for(i=2;i<=p;i++)
lg[i]=lg[i/2]+1;
for(i=1;i<=p;i++)
rmq[0][i]=e[i];
for(i=1;(1<<i)<=p;i++)
for(j=1;j+(1<<i)<=p;j++)
{
int len=(1<<(i-1));
rmq[i][j]=rmq[i-1][j];
if(niv[rmq[i-1][j+len]]<niv[rmq[i][j]])
rmq[i][j]=rmq[i-1][j+len];
}
}
int main()
{
int i,s,vx,vy;
Citire();
niv[1]=1;
DFS(1);
SkemaTovarasuluiEuler(1);
MakeRMQ();
for(i=1;i<=P;i++)
{
int poz1=poz[x];
int poz2=poz[y];
if(poz1>poz2)
swap(poz1,poz2);
int expo=lg[poz2-poz1+1];
int len=(1<<expo);
int lca1=rmq[expo][x];
int lca2=rmq[expo][y-len+1];
if(niv[lca1]>niv[lca2])
s=lca1;
else s=lca2;
sol[++t]=s;
vx=x;
vy=y;
x=(vx*a+vy*b)%n+1;
x=(vy*c+s*d)%n+1;
}
for(i=t-P+1;i<=t;i++)
fout<<sol[i]<<"\n";
return 0;
}