Pagini recente » Cod sursa (job #1973345) | Cod sursa (job #2173941) | Cod sursa (job #868481) | Cod sursa (job #113095) | Cod sursa (job #933446)
Cod sursa(job #933446)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
vector<pair<int,int> > v[32002];
int n,m,p,nre;
int f[32002];
int niv[3*32002];
int lg[3*32002];
int euler[3*32002];
int rmq[3*32002][20];
int t[3*32002][20];
int sol[3*32002][20];
bool used[32003];
void dfs(int nod, int nivel)
{
used[nod] = true;
euler[++nre] = nod;
niv[nre] = nivel;
f[nod] = nre;
for(unsigned int i=0;i<v[nod].size();i++)
if(!used[v[nod][i].first])
{
sol [ v[nod][i].first][0] = v[nod][i].second;
t[ v[nod][i].first ][0] = nod;
dfs(v[nod][i].first,nivel+1);
euler[++nre] = nod;
niv[nre] = nivel;
}
}
int query(int nod, int dist)
{
int r = 99999999;
while(dist)
{
int l = lg[dist];
r = min(r, sol[nod][l]);
nod = t[nod][l];
dist-=(1<<l);
}
return r;
}
//LCA
int LCA(int x, int y)
{
int i = f[x];
int j = f[y];
if( i > j)
swap(i,j);
int k = lg[j-i+1];
if( niv[ rmq[i][k] ] < niv[ rmq[j-(1<<k)+1][k] ] );
return euler[rmq[i][k]];
return euler[rmq[j - (1<<k) + 1][k]];
}
int main()
{
//citire
int x,y;
fin>>n>>m>>p;
int nrn = n;
for(int i=2;i<=n;i++)
{
fin>>x>>y;
v[x].push_back(make_pair(i,y));
v[i].push_back(make_pair(x,y));
}
dfs(1,0);
//rmq
n = nre;
for(int i=1;i<=n;i++)
{
rmq[i][0] = i;
if(i>1)
lg[i] = lg[i>>1] + 1;
}
for(int k=1 ; (1<<k)<=n;k++)
for(int i=1; i + (1<<k) - 1<=n;i++)
if(niv[ rmq[i][k-1] ] < niv[ rmq[i+(1<<(k-1))][k-1] ] )
rmq[i][k] = rmq[i][k-1];
else rmq[i][k] = rmq[i+(1<<(k-1))][k-1];
for(int k=1; (1<<k)<=n;k++)
for(int i=1;i<=n;i++)
{
t[i][k] = t[ t[i][k-1] ][k-1];
sol[i][k] = min(sol[i][k-1], sol[t[i][k-1]][k-1]);
}
//queryuri
int X,Y,A,B,C,D,Z;
fin>>X>>Y>>A>>B>>C>>D;
for(int i=1 ; i<=m ;i ++ )
{
if(X==Y)
Z = 0;
else
Z = min( query( X, niv[f[x]] - niv[f[LCA(X,Y)]]+1), query( Y,niv[f[Y]] - niv[f[LCA(X,Y)]] +1));
if(i>=m-p+1)
fout<<Z<<'\n';
X = (X*A + Y*B)%nrn + 1;
Y = (Y*C + Z*D)%nrn + 1;
}
fin.close();
fout.close();
return 0;
}