Pagini recente » Cod sursa (job #1219879) | Cod sursa (job #2685224) | Cod sursa (job #1603571) | Cod sursa (job #2005333) | Cod sursa (job #2570969)
#include <bits/stdc++.h>
#define FILE_NAME "atac"
#define fast ios_base :: sync_with_stdio(0); cin.tie(0);
#pragma GCC optimize("O3")
#define NMAX 32000 + 100
using namespace std;
ifstream f(FILE_NAME ".in");
ofstream g(FILE_NAME ".out");
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> llp;
typedef pair<ld,ld> pct;
const ll inf = 1LL << 60;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;
void add(ll &a , ll b)
{
a += b;
a %= mod;
}
void sub(ll &a, ll b)
{
a = (a - b + mod) % mod;
}
int n, m, p, ne, x, y,A, B, C, D ,X1, Y1;
vector <pi> G[NMAX];
int pd[18][NMAX], lvl[NMAX], euler[2*NMAX], str[18][NMAX], cost[18][NMAX],
niv[2*NMAX], ln[2*NMAX], lst[NMAX], dist[NMAX];
void DFS(int nod)
{
euler[++ne] = nod;
niv[ne] = lvl[nod];
for(auto it : G[nod])
{
int urm = it.first;
dist[urm] = it.second + dist[nod];
lvl[urm] = lvl[nod] + 1;
str[0][it.first] = nod;
cost[0][it.first] = it.second;
DFS(urm);
euler[++ne] = nod;
niv[ne] = lvl[nod];
}
lst[nod] = ne;
}
void RMQ()
{
for(int i = 2; i <= ne; ++i)
ln[i] = 1 + ln[i >> 1];
for(int i = 1; i <= ne; ++i)
pd[0][i] = i;
for(int i = 1; i <= ln[ne]; ++i)
{
int k = 1 << (i - 1);
for(int j = 1; j <= ne; ++j) ///pd[i][j] = min(pd[i-1][j], pd[i-1][j + k])
if(niv[ pd[i - 1][j] ] < niv[ pd[i - 1][j + k] ])
pd[i][j] = pd[i - 1][j];
else
pd[i][j] = pd[i - 1][j + k];
}
}
int LCA(int x, int y)
{
int a = min(lst[x], lst[y]);
int b = max(lst[x], lst[y]);
int d = ln[b - a + 1];
int ans = pd[d][a];
if(niv[ ans ] > niv[ pd[d][b - (1 << d) + 1] ])
ans = pd[d][b - (1 << d) + 1];
return euler[ans];
}
void precalc()
{
for(int i = 1; (1 << i) <= n; ++i)
for(int j = 1; j <= n; ++j)
{
str[i][j] = str[i - 1][ str[i - 1][j] ];
cost[i][j] = min(cost[i - 1][j], cost[i - 1][ str[i - 1][j] ]);
}
}
int main()
{
f >> n >> m >> p;
for(int i = 2; i <= n; ++i)
{
f >> x >> y;
G[x].push_back({i,y});
}
DFS(1);
RMQ();
precalc();
f >> X1 >> Y1 >> A >> B >> C >> D;
for(int i = 1; i <= m; ++i)
{
int mini = 1 << 30;
if(X1 != Y1)
{
int stramos = LCA(X1, Y1);
int cx = X1;
int cy = Y1;
int difx = lvl[cx] - lvl[stramos];
int dify = lvl[cy] - lvl[stramos];
int up = 0;
while(difx > 0 && X1 > 0)
{
if(difx & 1)
{
mini = min(mini, cost[up][X1]);
X1 = str[up][X1];
}
up++;
difx >>= 1;
}
up = 0;
while(dify > 0 && Y1 > 0)
{
if(dify & 1)
{
mini = min(mini, cost[up][Y1]);
Y1 = str[up][Y1];
}
up++;
dify >>= 1;
}
if(mini == 1 << 30)
mini = 0;
X1 = cx;
Y1 = cy;
}
else
mini = 0;
if(m - i < p)
g << mini << '\n';
X1 = (X1 * A + Y1 * B) % n + 1;
Y1 = (Y1 * C + mini * D) % n + 1;
}
f.close();
g.close();
return 0;
}