Pagini recente » Cod sursa (job #92212) | Cod sursa (job #855712) | Cod sursa (job #778748) | Cod sursa (job #2539979) | Cod sursa (job #1385856)
/*
Keep It Simple!
*/
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
ifstream fin("atac.in");
ofstream fout("atac.out");
const int kMaxN = 32005;
const int kInf = 0x3f3f3f3f;
typedef pair<int,int> pii;
long long N,M,P,X,Y,A,B,C,D;
vector<pii> G[kMaxN];
int lb[kMaxN];
pii dp[20][kMaxN],t[kMaxN];
int euler[kMaxN],lvl[kMaxN],first[kMaxN];
int ultim,rmq[20][kMaxN];
void ComputeLb() // ok
{
lb[1] = 0;
for(int i=2;i < kMaxN; ++i)
lb[i] = lb[i>>1] + 1;
}
void ReadInput() // ok
{
fin >> N >> M >> P;
int x,y;
for(int i=2; i<=N; ++i)
{
fin >> x >> y;
G[i].pb(mp(x,y));
G[x].pb(mp(i,y));
}
fin >> X >> Y >> A >> B >> C >> D;
}
void ComputeDpNdRmq()
{
for(int i=1; i<=N; ++i)
for(int j=1; (1<<j) <= N; ++j)
dp[j][i].fi = -1;
for(int i=1; i<=N; ++i)
dp[0][i] = t[i];
for(int i=1; i<=ultim; ++i)
rmq[0][i] = euler[i];
for(int i=1; (1<<i) <=N; ++i)
for(int j=1; j<=N; ++j)
if(dp[i-1][j].fi != -1)
{
dp[i][j].fi = dp[i-1][dp[i-1][j].fi].fi;
dp[i][j].se = min(dp[i-1][dp[i-1][j].fi].se,dp[i-1][j].se);
}
for(int i=1; (1<<i)<ultim; ++i)
for(int j=1; j <= ultim - (1<<i); ++j)
{
int len = 1 << (i-1);
rmq[i][j] = rmq[i-1][j];
if(lvl[rmq[i][j]] > lvl[rmq[i-1][j+len]])
rmq[i][j] = rmq[i-1][j+len];
}
}
void ComputeDFS(int node,int level) // ok
{
euler[++ultim] = node;
lvl[ultim] = node;
first[node] = ultim;
for(auto it:G[node])
if(t[it.fi].fi != node)
{
t[it.fi].fi = node;
t[it.fi].se = it.se;
ComputeDFS(it.fi,level+1);
euler[++ultim] = node;
lvl[ultim] = level;
}
}
int GetLCA(int x,int y)
{
int a = first[x], b = first[y];
if( a > b ) swap(a,b);
//find LCA
int diff = (b-a+1);
int lg = lb[diff];
int sh = diff - (1<<lg);
int ans = rmq[lg][a];
if(lvl[rmq[lg][a]] > lvl[rmq[lg][a+sh]])
ans = rmq[lg][a+sh];
return euler[ans];
}
int query(int x,int y)
{
if(x == y) return 0;
int Lc = GetLCA(x,y);
int ans = kInf;
for(int idx = lb[lvl[first[x]]]; idx; --idx)
if(lvl[first[x]] - (1<<idx) >= lvl[first[Lc]])
{
ans = min(ans,dp[idx][x].se);
x = dp[idx][x].fi;
}
for(int idx = lb[lvl[first[y]]]; idx; --idx)
if(lvl[first[y]] - (1<<idx) >= lvl[first[Lc]])
{
ans = min(ans,dp[idx][y].se);
y = dp[idx][y].fi;
}
return ans;
}
void Solve() // ok
{
ComputeLb();
ReadInput();
ComputeDFS(1,0);
ComputeDpNdRmq();
while(M--)
{
int Z = query(X,Y);
if(M<P)
fout << Z << '\n';
X = (X*A + Y*B) % N+1;
Y = (Y*C + Z*D) % N+1;
}
}
int main() // ok
{
Solve();
return 0;
}