Pagini recente » Cod sursa (job #1228461) | Cod sursa (job #2871942) | Cod sursa (job #1977258) | Cod sursa (job #2719456) | Cod sursa (job #933509)
Cod sursa(job #933509)
//sursa mihaivisuian, test pt kbs
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int t[16][32001],cst[16][32001],log[3*32001],rmq[3*32001][16],niv[3*32001],first[32001],euler[3*32001];
int n,m,p,x,y,a,b,c,d,z,nr;
vector<pair<int,int> >g[32001];
bool vis[32001];
void Dfs(int x, int lvl)
{
vis[x]=true;
euler[++nr]=x;
first[x]=nr;
niv[nr]=lvl;
for(vector<pair<int,int> >::iterator it=g[x].begin(); it<g[x].end(); it++)
{
if(!vis[it->first])
{
t[0][it->first]=x;
cst[0][it->first]=it->second;
Dfs(it->first,lvl+1);
euler[++nr]=x;
niv[nr]=lvl;
}
}
}
int Lca(int x, int y)
{
x=first[x],y=first[y];
if(x>y) swap(x,y);
int l=log[y-x+1];
if(niv[rmq[x][l]]<niv[rmq[y-(1<<l)+1][l]])
return euler[rmq[x][l]];
return euler[rmq[y-(1<<l)+1][l]];
}
int GetRes(int nod, int dist)
{
int res = 999999;
while(dist)
{
res = min(res,cst[log[dist]][nod]);
nod=t[log[dist]][nod];
dist-=(1<<log[dist]);
}
return res;
}
int Query(int x, int y)
{
if(x==y) return 0;
int nod= Lca(x,y);
int road1 = GetRes(x,niv[first[x]]-niv[first[nod]]);
int road2 = GetRes(y,niv[first[y]]-niv[first[nod]]);
return min(road1,road2);
}
int main()
{
fin>>n>>m>>p;
for(int i = 2; i<= n; i++ )
{
fin>>x>>c;
g[x].push_back(make_pair(i,c));
g[i].push_back(make_pair(x,c));
}
fin>>x>>y>>a>>b>>c>>d;
Dfs(1,0);
for(int i = 1; i<= nr; i++ )
{
rmq[i][0]=i;
if(i>1) log[i]=1+log[i>>1];
}
for(int j = 1; (1<<j)<= nr; j++ )
for(int i = 1; i +(1<<j)-1 <= nr; i++ )
if(niv[rmq[i][j-1]] < niv[rmq[i+(1<<(j-1))][j-1]])
rmq[i][j]=rmq[i][j-1];
else rmq[i][j]=rmq[i+(1<<(j-1))][j-1];
for(int i = 1; i <= log[n]; i++ )
{
for(int j = 1; j<= n; j++ )
{
t[i][j]=t[i-1][t[i-1][j]];
cst[i][j]=min(cst[i-1][j],cst[i-1][t[i-1][j]]);
}
}
while(m>p)
{
z = Query(x,y);
x=(a*x+y*b)%n+1;
y=(y*c+z*d)%n+1;
m--;
}
while(m)
{
m--;
int sol = Query(x,y);
x=(a*x+b*y)%n+1;
y=(y*c+sol*d)%n+1;
fout<<sol<<'\n';
}
fin.close();
fout.close();
return 0;
}