Pagini recente » Cod sursa (job #3261328) | Cod sursa (job #3227337) | Cod sursa (job #3280460) | Cod sursa (job #2613558) | Cod sursa (job #2867987)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int nmax=32000, n2max=15, inf=(1<<30)-1;
vector <int> g[nmax+1];
int rmq[n2max+1][2*nmax], pv[nmax+1], l[nmax+1], lg[2*nmax];
int v[n2max][nmax+1],f[n2max][nmax+1];
int poz=0;
void dfs(int x){
poz++;
rmq[0][poz]=x;
pv[x]=poz;
for(int i=0;i<int(g[x].size());i++){
int xn=g[x][i];
l[xn]=l[x]+1;
dfs(xn);
poz++;
rmq[0][poz]=x;
}
}
int Min(int a,int b){
if(a<b){
return a;
}else{
return b;
}
}
int main(){
int n,m,p;
fin>>n>>m>>p;
for(int i=2;i<=n;i++){
int x,y;
fin>>x>>y;
g[x].push_back(i);
v[0][i]=y;
f[0][i]=x;
}
v[0][0]=inf;
v[0][1]=inf;
for(int i=2;i<2*nmax;i++){
lg[i]=lg[i/2]+1;
}
for(int i=1;i<=lg[n];i++){
for(int j=1;j<=n;j++){
f[i][j]=f[i-1][f[i-1][j]];
v[i][j]=Min(v[i-1][j],v[i-1][f[i-1][j]]);
}
}
l[1]=1;
dfs(1);
for(int i=1;i<=lg[poz];i++){
for(int j=1;j<=poz-(1<<i)+1;j++){
if(l[rmq[i-1][j]]<l[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 x,y,a,b,c,d;
fin>>x>>y>>a>>b>>c>>d;
for(int i=1;i<=m;i++){
int x2=x,y2=y;
x=pv[x];
y=pv[y];
if(x>y){
int aux=x;
x=y;
y=aux;
}
int log2=lg[y-x+1],lca;
if(l[rmq[log2][x]]<l[rmq[log2][y+1-(1<<log2)]]){
lca=rmq[log2][x];
}else{
lca=rmq[log2][y+1-(1<<log2)];
}
x=x2;
y=y2;
int aux=l[x]-l[lca], auy=l[y]-l[lca];
int minx=inf;
for(int j=0;(1<<j)<=aux;j++){
if((aux&(1<<j))!=0){
minx=Min(minx,v[j][x]);
x=f[j][x];
}
}
for(int j=0;(1<<j)<=auy;j++){
if((auy&(1<<j))!=0){
minx=Min(minx,v[j][y]);
y=f[j][y];
}
}
if(minx==inf){
minx=0;
}
if(i>=m-p+1){
fout<<minx<<"\n";
}
x=(x2*a+y2*b)%n+1;
y=(y2*c+minx*d)%n+1;
}
return 0;
}