Pagini recente » Cod sursa (job #2836295) | Cod sursa (job #634537) | Cod sursa (job #1061295) | Cod sursa (job #1061467) | Cod sursa (job #2329060)
#include <fstream>
#include <vector>
#include <iostream>
#define DIM 32005
#define INF 2000000000
using namespace std;
ifstream fi("atac.in");
ofstream fo("atac.out");
int n,m,p;
vector<pair<int,int> > V[DIM];
int A[20][DIM],mn[20][DIM],l[DIM];
int x,y,z,a,b,c,d;
void dfs(int nod)
{
l[nod]=l[A[0][nod]]+1;
for(auto it:V[nod])
if(!l[it.first])
{
A[0][it.first]=nod,mn[0][it.first]=it.second;
dfs(it.first);
}
}
pair<int,int> stramos(int q,int p)
{
if(p==0)
return {q,0};
if(l[q]<=p)
return {0,INF};
int rez=q,rmn=INF;
for(int i=30;i>=0;i--)
if(p&(1<<i))
rmn=min(rmn,mn[i][rez]),rez=A[i][rez];
return {rez,rmn};
}
int query(int a,int b)
{
if(a==b)
return 0;
if(l[a]<l[b])
swap(a,b);
pair<int,int> aux=stramos(a,l[a]-l[b]);
a=aux.first;
int rez=aux.second,st,dr;
if(a==b)
return rez;
for(st=0,dr=n;st<dr;)
{
int mid=(st+dr)/2;
//cout<<a<<" "<<b<<" ";
pair<int,int> aux1=stramos(a,mid),aux2=stramos(b,mid);
//cout<<mid<<" "<<aux1.first<<" "<<aux2.first<<"\n";
if(aux1.first==aux2.first)
{
dr=mid;
rez=min(aux1.second,aux2.second);
}
else
st=mid+1;
}
return rez;
}
int main()
{
fi>>n>>m>>p;
for(int i=2;i<=n;i++)
{
int a,b;fi>>a>>b;
V[i].push_back({a,b});
V[a].push_back({i,b});
}
dfs(1);
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j<=n;j++)
{
A[i][j]=A[i-1][A[i-1][j]];
mn[i][j]=min(mn[i-1][j],mn[i-1][A[i-1][j]]);
}
/*
pair<int,int> p=stramos(7,1);
cout<<p.first<<" "<<p.second<<"\n";
*/
fi>>x>>y>>a>>b>>c>>d;
z=query(x,y);
for(int i=2;i<=m;i++)
{
x=(1LL*x*a+1LL*y*b)%n+1;
y=(1LL*y*c+1LL*z*d)%n+1;
z=query(x,y);
if(i>m-p)
fo<<z<<"\n";
}
fi.close();
fo.close();
return 0;
}