Pagini recente » Cod sursa (job #1339841) | Cod sursa (job #3037776) | Cod sursa (job #693142) | Cod sursa (job #3280961) | Cod sursa (job #2286008)
#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);
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 k = 1; k < 15; ++k) {
for (int i = (1<<k) - 1; i < euler.size(); ++i) {
rl[i][k] = rl[i][k - 1];
if (h[rl[i][k]] > h[rl[i - (1<<(k - 1))][k - 1]])
rl[i][k] = rl[i - (1<<(k - 1))][k - 1];
}
for (int i = 1; i <= n; ++i)
str[i][k] = str[str[i][k - 1]][k - 1],
rf[i][k] = min(rf[i][k - 1], rf[str[i][k - 1]][k - 1]);
}
}
int lca(int x, int y) {
if (pl[x] > pl[y])
swap(x, y);
x = pl[x];
y = pl[y];
int ll = l[y - x + 1];
int a = rl[y][ll];
int b = rl[x + (1<<ll) - 1][ll];
if (h[a] > h[b])
a = b;
return a;
}
int f(int x, int y) {
if (y == 0)
return 0;
if (h[x] < y)
return 0;
int r(0), pas = 15, 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;
}