Pagini recente » Cod sursa (job #2450891) | Cod sursa (job #2943325) | Cod sursa (job #1837743) | Cod sursa (job #3000044) | Cod sursa (job #2400511)
#include <fstream>
#include <cmath>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int oo = 2000000000;
const int nMax = 32000;
int n, m, p, a, b, c, d, x, y;
vector<pair<int, int>> g[nMax + 5];
int sol[500005];
int use[nMax + 5], eulvl[2 * nMax + 5], eul[2 * nMax + 5], first[nMax + 5];
int lvl[nMax + 5], dim, cost[18][nMax + 5], st[18][nMax + 5];
int rmq[18][2 * nMax + 5];
void DFS(int nod, int lev) {
use[nod] = 1;
lvl[nod] = lev;
eul[++dim] = nod;
eulvl[dim] = lev;
first[nod] = dim;
for (auto i : g[nod])
if (!use[i.first]) {
st[0][i.first] = nod;
cost[0][i.first] = i.second;
DFS(i.first, lev + 1);
eul[++dim] = nod;
eulvl[dim] = lev;
}
}
void Build() {
for (int i = 1; (1 << i) <= n; i++)
for (int j = 1; j <= n; j++) {
st[i][j] = st[i - 1][st[i - 1][j]];
cost[i][j] = min(cost[i - 1][j], cost[i - 1][st[i - 1][j]]);
}
}
void RMQ() {
for (int i = 1; i <= dim; i++)
rmq[0][i] = i;
for (int i = 1; (1 << i) < dim; i++)
for (int j = 1; j <= dim - (1 << i); j++) {
rmq[i][j] = rmq[i - 1][j];
int salt = 1 << (i - 1);
if (eulvl[rmq[i][j]] > eulvl[rmq[i - 1][j + salt]])
rmq[i][j] = rmq[i - 1][j + salt];
}
}
int LCA(int p, int k) {
p = first[p];
k = first[k];
if (p > k)
swap(p, k);
int dif = k - p;
int lg = log2(dif);
int sol = rmq[lg][p];
if (eulvl[sol] > eulvl[rmq[lg][k -(1 << lg) + 1]])
sol = rmq[lg][k -(1 << lg) + 1];
return eulvl[sol];
}
int main() {
fin >> n >> m >> p;
for (int i = 2; i <= n; i++) {
int u, v;
fin >> u >> v;
g[u].push_back({i, v});
g[i].push_back({u, v});
}
fin >> x >> y >> a >> b >> c >> d;
DFS(1, 0);
RMQ();
Build();
for (int i = 1; i <= m; i++) {
int stlvl = LCA(x, y);
int keepx = x, keepy = y;
int xl = - (stlvl - lvl[x]);
int yl = - (stlvl - lvl[y]);
int urc = 0;
sol[i] = oo;
while (xl > 0 && x > 0) {
if (xl & 1) {
sol[i] = min(sol[i], cost[urc][x]);
x = st[urc][x];
}
urc++;
xl /= 2;
}
urc = 0;
while (yl > 0 && y > 0) {
if (yl & 1) {
sol[i] = min(sol[i], cost[urc][y]);
y = st[urc][y];
}
urc++;
yl /= 2;
}
x = (keepx * a + keepy * b) % n + 1;
y = (keepy * c + sol[i] * d) % n + 1;
}
for (int i = m - p + 1; i <= m; i++)
fout << sol[i] << '\n';
}