Pagini recente » Cod sursa (job #1215508) | Cod sursa (job #1066637) | Cod sursa (job #366670) | Cod sursa (job #2668469) | Cod sursa (job #1954774)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("atac.in");
ofstream out("atac.out");
int n,m,p;
int X,Y,A,B,C,D;
vector<int> L[32005];
struct par{
int nod, cost;
}PAR[32005];
int LOG2[64005];
int es, EULER[64005],NIV[64005],FOCC[32005];
int RMQ[15][65005];
int MIN[15][32005];
int STR[15][32005];
void next(int z){
X=(X*A + Y*B)%n +1;
Y=(Y*C + z*D)%n +1;
}
void read(){
int x,y;
in>>n>>m>>p;
for(int i=1;i<n;i++){
in>>x>>y;
L[x].push_back(i+1);
L[i+1].push_back(x);
PAR[i+1]={x,y};
}
in>>X>>Y>>A>>B>>C>>D;
}
void logs(){
for(int i=2;i<=es;i++){
LOG2[i]=LOG2[i/2]+1;
}
}
void euler(int nod, int par, int niv){
es++;
EULER[es]=nod;
NIV[es]=niv;
if(!FOCC[nod])
FOCC[nod]=es;
for(auto x : L[nod]){
if(x!=par){
euler(x,nod,niv+1);
es++;
EULER[es]=nod;
NIV[es]=niv;
}
}
}
void prep_rmq(){
for(int i=1;i<=es;i++){
RMQ[0][i]=i;
}
for(int i=1;(1<<i)<=es;i++){
for(int j=1;j<=es;j++){
if(NIV[RMQ[i-1][j]] < NIV[RMQ[i-1][j+(1<<(i-1))]])
RMQ[i][j]=RMQ[i-1][j];
else RMQ[i][j]=RMQ[i-1][j+(1<<(i-1))];
}
}
}
int lca(int x, int y){
int lo,hi,nr_elem,log_elem;
lo=min(FOCC[x],FOCC[y]);
hi=max(FOCC[x],FOCC[y]);
nr_elem=hi-lo+1;
log_elem=LOG2[nr_elem];
if(NIV[RMQ[log_elem][lo]] < NIV[RMQ[log_elem][lo+nr_elem-(1<<log_elem)]])
return EULER[RMQ[log_elem][lo]];
else return EULER[RMQ[log_elem][lo+nr_elem-(1<<log_elem)]];
}
void prep_min(){
for(int i=1;i<=n;i++){
MIN[0][i]=PAR[i].cost;
STR[0][i]=PAR[i].nod;
}
for(int i=1;(1<<i)<=n;i++){
for(int j=1;j<=n;j++){
STR[i][j]=STR[i-1][STR[i-1][j]];
MIN[i][j]=min(MIN[i-1][j],MIN[i-1][STR[i-1][j]]);
}
}
}
int minimum(int nod, int lungime){
int mini=1<<30,l;
while(lungime!=0){
l=LOG2[lungime];
mini=min(mini,MIN[l][nod]);
lungime-=(1<<l);
nod=STR[l][nod];
}
return mini;
}
void prep(){
euler(L[2].front(),-1,1);
logs();
prep_rmq();
prep_min();
}
void solve(){
int lc,d1,d2;
prep();
for(int i=1;i<=m-p;i++){
lc=lca(X,Y);
d1=NIV[FOCC[X]]-NIV[FOCC[lc]];
d2=NIV[FOCC[Y]]-NIV[FOCC[lc]];
next(min(minimum(X,d1),minimum(Y,d2)));
}
for(int i=1;i<=p;i++){
int m1,m2;
lc=lca(X,Y);
d1=NIV[FOCC[X]]-NIV[FOCC[lc]];
d2=NIV[FOCC[Y]]-NIV[FOCC[lc]];
m1=minimum(X,d1);
m2=minimum(Y,d2);
next(min(m1,m2));
out<<min(m1,m2)<<"\n";
}
}
int main(){
read();
solve();
return 0;
}