Pagini recente » Cod sursa (job #489420) | Cod sursa (job #716747) | Cod sursa (job #86461) | Cod sursa (job #717362) | Cod sursa (job #1145850)
#include<fstream>
#include<vector>
#define MAXN 32001
using namespace std;
int n,x,y,z,a,b,c,d,m,nr,u,maxlvl;
int din[MAXN][20],p[MAXN][20],lvl[2*MAXN][20],eul[2*MAXN][20],poz[MAXN];
vector<pair<int,int> >g[MAXN];
ifstream fin("atac.in");
ofstream fout("atac.out");
void citire()
{
int p,q;
fin>>n>>m>>nr;
for(int i=2;i<=n;i++)
{
fin>>p>>q;
g[i].push_back(make_pair(p,q));
g[p].push_back(make_pair(i,q));
}
fin>>x>>y>>a>>b>>c>>d;
}
void dfs(int nod,int niv)
{
if(niv>maxlvl)
maxlvl=niv;
eul[++u][0]=nod;
lvl[u][0]=niv;
poz[nod]=u;
for(int i=0;i<g[nod].size();i++)
{
if(poz[g[nod][i].first]==0)
{
p[g[nod][i].first][0]=nod;
din[g[nod][i].first][0]=g[nod][i].second;
dfs(g[nod][i].first,niv+1);
eul[++u][0]=nod;
lvl[u][0]=niv;
}
}
}
void rmq()
{
int p2;
for(int i=1;(1<<i)<=u;i++)
{
p2=(1<<(i-1));
for(int j=1;j<=u-p2;j++)
{
if(lvl[j][i-1]<lvl[j+p2][i-1])
{
lvl[j][i]=lvl[j][i-1];
eul[j][i]=eul[j][i-1];
}
else
{
lvl[j][i]=lvl[j+p2][i-1];
eul[j][i]=eul[j+p2][i-1];
}
}
}
}
void preproc()
{
for(int i=1;(1<<i)<=maxlvl;i++)
{
for(int j=1;j<=n;j++)
{
if((1<<i)>lvl[poz[j]][0])
continue;
p[j][i]=p[p[j][i-1]][i-1];
din[j][i]=min(din[j][i-1],din[p[j][i-1]][i-1]);
}
}
}
inline int pow2(int x)
{
int i;
for( i=0;(1<<i)<=x;i++);
return i-1;
}
inline int Minim(int x,int y)
{
int sol=1000000;
int niv=lvl[poz[x]][0]-lvl[poz[y]][0];
for(int i=pow2(niv);x!=y;x=p[x][i])
{
sol=min(sol,din[x][i]);
niv=lvl[poz[x]][0]-lvl[poz[y]][0];
i=pow2(niv);
}
return sol;
}
int query(int x,int y)
{
int st=min(poz[x],poz[y]),sf=poz[x]+poz[y]-st;
int l=pow2(sf-st+1);
int lca=(lvl[st][l]<lvl[sf-(1<<l)+1][l])?eul[st][l]:eul[sf-(1<<l)+1][l];
return min(Minim(x,lca),Minim(y,lca));
}
int main()
{
citire();
dfs(1,1);
rmq();
preproc();
for(int i=1;i<=m;i++)
{
z=query(x,y);
x=(x*a+y*b)%n+1;
y=(y*c+z*d)%n+1;
if(i>=m-nr+1)
fout<<z<<"\n";
}
return 0;
}