Pagini recente » Cod sursa (job #2829834) | Cod sursa (job #1900720) | Cod sursa (job #104987) | Cod sursa (job #1758705) | Cod sursa (job #1384889)
#include <fstream>
#include <vector>
using namespace std;
typedef pair<int, int> Pair;
const int kMaxN = 32005, kMaxLog = 16, kInf = 0x3f3f3f3f;
ifstream fin("atac.in");
ofstream fout("atac.out");
int N, M, P, X, Y, A, B, C, D;
vector<Pair> G[kMaxN];
bool use[kMaxN];
int lg2[kMaxN << 1];
Pair anc[kMaxLog][kMaxN];
int level[kMaxN], rmq[kMaxLog][kMaxN << 1], euler_crt, first[kMaxN];
void DFS(int node) {
use[node] = true;
rmq[0][++euler_crt] = node;
first[node] = euler_crt;
for (auto it : G[node])
if (!use[it.first]) {
level[it.first] = level[node] + 1;
anc[0][it.first] = Pair(node, it.second);
DFS(it.first);
rmq[0][++euler_crt] = node;
}
}
inline int MinLevel(int a, int b) {
return level[a] < level[b] ? a : b;
}
int LCA(int x, int y) {
x = first[x];
y = first[y];
if (x > y)
swap(x, y);
int lg = lg2[y - x];
return MinLevel(rmq[lg][x], rmq[lg][y - (1 << lg) + 1]);
}
int MinEdge(int node, int ancestor) {
int dif = level[node] - level[ancestor], ans = kInf;
for (int step = 0; step < kMaxLog; ++step)
if (dif & (1 << step)) {
ans = min(ans, anc[step][node].second);
node = anc[step][node].first;
}
return ans;
}
int main() {
fin >> N >> M >> P;
for (int i = 2; i <= N; ++i) {
int u, v;
fin >> u >> v;
G[i].emplace_back(u, v);
G[u].emplace_back(i, v);
}
fin >> X >> Y >> A >> B >> C >> D;
level[1] = 1;
DFS(1);
for (int i = 2; i < (kMaxN << 1); ++i)
lg2[i] = lg2[i >> 1] + 1;
for (int i = 1; i < kMaxLog; ++i) {
for (int j = 1; j <= N; ++j) {
anc[i][j].first = anc[i - 1][anc[i - 1][j].first].first;
anc[i][j].second = min(anc[i - 1][j].second, anc[i - 1][anc[i - 1][j].first].second);
}
for (int j = 1; j <= euler_crt - (1 << i) + 1; ++j)
rmq[i][j] = MinLevel(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
}
while (M--) {
int lca = LCA(X, Y);
int ans = (X == Y) ? 0 : min(MinEdge(X, lca), MinEdge(Y, lca));
if (M < P)
fout << ans << "\n";
X = (X * A + Y * B) % N + 1;
Y = (Y * C + ans * D) % N + 1;
}
return 0;
}