Pagini recente » Cod sursa (job #489465) | Cod sursa (job #1561693) | Cod sursa (job #451070) | Cod sursa (job #556433) | Cod sursa (job #1958661)
#include <fstream>
#include <vector>
using namespace std;
const int kLog = 30;
struct Node
{
int ancestors[kLog];
int anc_len = 0;
int costs[kLog];
int costs_len = 0;
int enter_time = 0, exit_time = 0;
vector<pair<int, int>> edges;
};
using Tree = vector<Node>;
int dfs_time = 0;
void Dfs(Tree &t, int node, vector<int> &st, int &nst)
{
t[node].enter_time = ++dfs_time;
st[nst++] = node;
if (nst != 1) {
int fa = st[nst - 2];
t[node].ancestors[0] = fa;
t[node].anc_len = 1;
for (int i = 1; fa > 0 && i < t[fa].anc_len; ++i) {
t[node].ancestors[i] = t[fa].ancestors[i - 1];
t[node].costs[i] = min(t[node].costs[i - 1], t[fa].costs[i - 1]);
fa = t[fa].ancestors[i - 1];
t[node].anc_len = t[node].costs_len = i + 1;
}
}
for (const auto &e : t[node].edges) {
int son = e.first;
if (t[son].enter_time == 0) {
t[son].costs[0] = e.second;
t[son].costs_len = 1;
Dfs(t, son, st, nst);
}
}
t[node].exit_time = ++dfs_time;
--nst;
}
void FindAncestors(Tree &t)
{
vector<int> st(t.size());
int nst = 0;
Dfs(t, 0, st, nst);
}
int FindMin(const Tree &t, int x, int y)
{
if (x == y) {
return 0;
}
int min_cost = (1 << 29);
while (x != y) {
if (t[x].exit_time > t[y].exit_time) {
swap(x, y);
}
int pos = 0;
int pow = (1 << 20);
while (pow > 0) {
if (pow + pos < t[x].anc_len) {
int fa = t[x].ancestors[pos + pow];
if (t[fa].exit_time < t[y].exit_time) {
pos += pow;
min_cost = min(min_cost, t[x].costs[pos]);
}
}
pow >>= 1;
}
x = t[x].ancestors[pos];
}
return min_cost;
}
int main()
{
ifstream fin("atac.in");
ofstream fout("atac.out");
int n, q, p;
fin >> n >> q >> p;
Tree tree(n);
for (int i = 1; i < n; ++i) {
int fa, cost;
fin >> fa >> cost;
tree[i].edges.push_back({fa - 1, cost});
tree[fa - 1].edges.push_back({i, cost});
}
FindAncestors(tree);
int x, y, a, b, c, d;
fin >> x >> y >> a >> b >> c >> d;
for (int i = 1; i <= q; ++i) {
int res = ((x == y) ? 0 : FindMin(tree, x - 1, y - 1));
if (q - i + 1 <= p) {
fout << res << "\n";
}
int new_x = (x * a + y * b) % (n + 1);
int new_y = (y * c + res * d) % (n + 1);
x = new_x;
y = new_y;
}
return 0;
}