Pagini recente » Borderou de evaluare (job #1565720) | Cod sursa (job #2652750) | Cod sursa (job #1969167) | Cod sursa (job #2609313) | Cod sursa (job #2604697)
#include <bits/stdc++.h>
#define Nmax 32005
#define LG 16
#define INF 1e9
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int N, K, Q, P, A, B, C, D, X, Y, L;
int lev[Nmax], le[Nmax], ri[Nmax], anc[Nmax][LG], dp[Nmax][LG];
vector<pair<int, int> > G[Nmax];
bool isAnc(int x, int y) {
return (le[x] <= le[y] && ri[y] <= ri[x]);
}
int lca(int x, int y) {
if (isAnc(x, y)) return x;
if (isAnc(y, x)) return y;
for (int i = L; i >= 0; --i)
if (!isAnc(anc[x][i], y)) x = anc[x][i];
return anc[x][0];
}
int calc(int x, int root) {
int ans = INF;
for (int i = L; i >= 0 && x != root; --i) {
int nxt = anc[x][i];
if (lev[x] < lev[root]) continue;
ans = min(ans, dp[x][i]);
x = nxt;
}
return ans;
}
void DFS(int node, int father, int len) {
lev[node] = lev[father] + 1;
le[node] = ++K;
anc[node][0] = father;
dp[node][0] = len;
for (int i = 1; i <= L; ++i) {
int mid = anc[node][i - 1];
anc[node][i] = anc[mid][i - 1];
dp[node][i] = min(dp[node][i - 1], dp[mid][i - 1]);
}
for (auto it: G[node])
if (it.first != father) DFS(it.first, node, it.second);
ri[node] = ++K;
}
int main()
{
f >> N >> Q >> P;
L = ceil(log2(N));
for (int i = 2; i <= N; ++i) {
int x, y;
f >> x >> y;
G[x].push_back({i, y});
G[i].push_back({x, y});
}
DFS(1, 1, INF);
f >> X >> Y >> A >> B >> C >> D;
for (int q = Q; q >= 1; --q) {
int Lca = lca(X, Y);
int ans = min(calc(X, Lca), calc(Y, Lca));
if (q <= P) g << ans << '\n';
X = (X * A + Y * B) % N + 1;
Y = (Y * C + ans * D) % N + 1;
}
return 0;
}