Pagini recente » Cod sursa (job #2031040) | Cod sursa (job #677658) | Cod sursa (job #1205814) | Cod sursa (job #52430) | Cod sursa (job #2285992)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
const int N = 33007;
vector < pair < int, int > > v[N];
vector < int > euler;
int pl[N], h[N], l[2 * N], cst[N], t[N], rl[2 * N][15], str[N][15], rf[N][15];
int in, n;
void pe_dfs(int nod = 1) {
euler.push_back(nod);
if (pl[nod] == 0)
pl[nod] = euler.size() - 1;
for (auto i : v[nod])
h[i.first] = h[nod] + 1, pe_dfs(i.first), euler.push_back(nod);
}
void precalc() {
pe_dfs();
for (int i = 0; i < 15; ++i)
for (int j = (1<<i); j < (1<<(i + 1)) && j < N; ++j)
l[j] = i;
for (int i = 0; i < euler.size(); ++i)
rl[i][0] = euler[i];
for (int i = 1; i <= n; ++i)
str[i][0] = t[i];
for (int i = 2; i <= n; ++i)
rf[i][0] = cst[i];
for (int p = 1; p < 15; ++p) {
for (int i = 0; i + (1<<p) <= euler.size(); ++i) {
if (h[rl[i][p - 1]] < h[rl[i + (1<<(p - 1))][p - 1]])
rl[i][p] = rl[i][p - 1];
else
rl[i][p] = rl[i + (1<<(p - 1))][p - 1];
}
for (int i = 1; i <= n; ++i)
str[i][p] = str[str[i][p - 1]][p - 1],
rf[i][p] = min(rf[i][p - 1], rf[str[i][p - 1]][p - 1]);
}
}
int lca(int x, int y) {
if (pl[x] > pl[y])
swap(x, y);
if (h[rl[pl[x]][l[pl[y] - pl[x] + 1]]] > h[rl[pl[y] - (1<<l[pl[y] - pl[x] + 1]) + 1][l[pl[y] - pl[x] + 1]]])
return rl[pl[y] - (1<<l[pl[y] - pl[x] + 1]) + 1][l[pl[y] - pl[x] + 1]];
return rl[pl[x]][l[pl[y] - pl[x] + 1]];
}
int f(int x, int y) {
if (y == 0)
return 0;
if (h[x] < y)
return 0;
int r(0), pas = 14, ans(1e9 + 7);
while (pas >= 0) {
if (r + (1<<pas) <= y)
ans = min(ans, rf[x][pas]),
r += (1<<pas),
x = str[x][pas];
--pas;
}
return ans;
}
int main()
{
int q, p, x, y, a, b, c, d;
cin >> n >> q >> p;
for (int i = 2; i <= n; ++i)
cin >> t[i] >> cst[i],
v[t[i]].push_back({i, cst[i]});
precalc();
cin >> x >> y >> a >> b >> c >> d;
while (q--) {
if (x == y) {
if (q < p)
cout << "0\n";
x = (1LL * x * a + 1LL * y * b) % n + 1;
y = 1LL * y * c % n + 1;
continue;
}
int piv = lca(x, y);
int min1 = f(x, h[x] - h[piv]), min2 = f(y, h[y] - h[piv]);
if (q < p)
cout << min(min1, min2) << '\n';
x = (1LL * x * a + 1LL * y * b) % n + 1;
y = (1LL * y * c + 1LL * min(min1, min2) * d) % n + 1;
}
return 0;
}