Pagini recente » Cod sursa (job #959486) | Cod sursa (job #663434) | Cod sursa (job #1795366) | Cod sursa (job #229134) | Cod sursa (job #2847455)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int INF(1e9), NMAX(1e5 + 5), LMAX(17);
int t[NMAX][LMAX], r[NMAX][LMAX], lvl[NMAX], l2[NMAX], p2[LMAX];
vector<pair<int, int>> g[NMAX];
inline void DFS(int const& x = 1) {
for (int i = 1; i < LMAX; ++i)
t[x][i] = t[t[x][i - 1]][i - 1];
for (int i = 1; i < LMAX; ++i)
r[x][i] = min(r[x][i - 1], r[t[x][i - 1]][i - 1]);
for (pair<int, int> const& P : g[x]) {
int y, w;
tie(y, w) = P;
if (y == t[x][0])
continue;
lvl[y] = lvl[x] + 1;
t[y][0] = x;
r[y][0] = w;
DFS(y);
}
}
inline int Query(int const& a, int const& b) {
int x = a, y = b, res = INF;
if (lvl[x] < lvl[y])
swap(x, y);
for (int i = l2[lvl[x] - lvl[y] + 1]; i >= 0; --i)
if (lvl[x] - p2[i] >= lvl[y]) {
res = min(res, r[x][i]);
x = t[x][i];
}
if (x == y)
return res;
for (int i = l2[lvl[x] + 1]; i >= 0; --i)
if (t[x][i] != t[y][i]) {
res = min({res, r[x][i], r[y][i]});
x = t[x][i];
y = t[y][i];
}
res = min({res, r[x][0], r[y][0]});
return res;
}
inline void Init() {
for (int i = 2; i < NMAX; ++i)
l2[i] = l2[i / 2] + 1;
p2[0] = 1;
for (int i = 1; i < LMAX; ++i)
p2[i] = p2[i - 1] * 2;
for (int i = 0; i < NMAX; ++i)
for (int j = 0; j < LMAX; ++j)
r[i][j] = INF;
}
int main() {
Init();
int n, m, p;
fin >> n >> m >> p;
for (int i = 2; i <= n; ++i) {
int j, w;
fin >> j >> w;
g[i].emplace_back(j, w);
g[j].emplace_back(i, w);
}
DFS();
int x, y, a, b, c, d;
fin >> x >> y >> a >> b >> c >> d;
while (m--) {
int z = Query(x, y);
if (z == INF) z = 0;
if (m < p) fout << z << '\n';
x = (x * a + y * b) % n + 1;
y = (y * c + z * d) % n + 1;
}
return 0;
}