Pagini recente » Cod sursa (job #2788276) | Cod sursa (job #1525471) | Cod sursa (job #617055) | Cod sursa (job #255857) | Cod sursa (job #1385534)
/*
Keep It Simple!
*/
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int kMaxN = 32005;
const int kInf = 0x3f3f3f;
int lb[kMaxN],lvl[2*kMaxN+100],euler[2*kMaxN+100],first[kMaxN];
ll n,m,p,ans,ultim;
ll x,y,a,b,c,d;
int rmq[16][kMaxN];
struct el
{
ll a,b;
}dp[16][kMaxN],t[kMaxN];
vector<pii> G[kMaxN];
void ComputeLb()
{
for(int i=2; i<kMaxN; ++i)
lb[i] = lb[i/2] + 1;
}
void DFS(int node,int level)
{
euler[++ultim] = node;
lvl[ultim] = level;
first[node] = ultim;
for(auto vecin : G[node])
if(!t[vecin.fi].a)
{
t[vecin.fi].a = node;
t[vecin.fi].b = vecin.se;
DFS(vecin.fi,level+1);
euler[++ultim] = node;
lvl[ultim] = level;
}
}
void ComputeDads()
{
t[1].a = -1;
DFS(1,0);
}
void ComputeLCA()
{
for(int i=1; i<=n; ++i)
for(int j=1; 1<<j <=n; ++j)
dp[j][i].a = -1;
for(int i=1; i<=n; ++i)
dp[0][i] = t[i];
for(int i=1; 1<<i <=n; ++i)
for(int j=1; j<=n; ++j)
{
dp[i][j].a = dp[i-1][dp[i-1][j].a].a;
dp[i][j].b = min(dp[i-1][dp[i-1][j].a].b,dp[i-1][j].b);
}
}
void ComputeRMQ()
{
for(int i=1; i<=ultim; ++i)
rmq[0][i] = i;
for(int i=1; (1<<i) < ultim; ++i)
for(int j=1; j <= ultim - (1<<i); ++j)
{
int pw = 1 << (i - 1);
rmq[i][j] = rmq[i-1][j];
if(lvl[rmq[i-1][j+pw]] < lvl[rmq[i][j]] )
rmq[i][j] = rmq[i-1][j+pw];
}
}
int LCA(int x, int y)
{
int a = first[x],b=first[y];
if(a>b) swap(a,b);
int lg = lb[b-a+1];
ans = rmq[lg][a];
int sh = (b-a+1) - ( 1 << lg );
if(lvl[ans] > 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 = LCA(x,y);
ans = kInf;
for(int idx = lb[lvl[first[x]]]; idx>=0; --idx)
if(lvl[first[x]] - (1<<idx) >= lvl[first[Lc]])
{
ans = min(ans,dp[idx][x].b);
x = dp[idx][x].a;
}
for(int idx = lb[lvl[first[y]]]; idx>=0; --idx)
if(lvl[first[y]] - (1<<idx) >= lvl[first[Lc]])
{
ans = min(ans,dp[idx][y].b);
y = dp[idx][y].a;
}
return ans;
}
void Solve()
{
fin >> n >> m >> p;
for(int i=2;i<=n;++i)
{
fin >> x >> y;
G[x].pb(mp(i,y));
G[i].pb(mp(x,y));
}
fin >> x >> y >> a >> b >> c >> d;
ComputeLb();
ComputeDads();
ComputeLCA();
ComputeRMQ();
int z; ++m;
while(m)
{
z = Query(x,y);
x = (x*a + y*b) % (n+1);
y = (y*c + z*d) % (n+1);
if(m <= p)
fout << z << '\n';
--m;
}
}
int main()
{
Solve();
return 0;
}