Pagini recente » Cod sursa (job #2875839) | Cod sursa (job #3221170) | Cod sursa (job #2489813) | Cod sursa (job #3243294) | Cod sursa (job #1651249)
#include <fstream>
#include <vector>
#include <algorithm>
#define pii pair< int, int >
#define st first
#define nd second
using namespace std;
const int Mn = 1 << 17;
const int Mlg = 17;
const int oo = 1 << 30;
int n, m, p, x, y, a, b, c, d, cnt;
int lg[Mn], depth[Mn], pos[Mn];
int rmq[Mlg][Mn];
bool used[Mn];
pii parent[Mlg][Mn];
vector< pii > g[Mn];
ifstream fi("atac.in");
ofstream fo("atac.out");
void dfs(int x)
{
used[x] = 1;
rmq[0][++cnt] = x;
pos[x] = cnt;
for (auto node : g[x])
if (!used[node.st])
{
depth[node.st] = depth[x] + 1;
parent[0][node.st] = pii(x, node.nd);
dfs(node.st);
rmq[0][++cnt] = x;
}
}
int min_depth(int u, int v)
{
return (depth[u] < depth[v] ? u : v);
}
int lca(int u, int v)
{
u = pos[u];
v = pos[v];
if (u > v)
swap(u, v);
int aux = lg[v - u];
return min_depth(rmq[aux][u], rmq[aux][v - (1 << aux) + 1]);
}
int min_value(int u, int v)
{
int aux = depth[u] - depth[v], sol = oo;
for (int i = 0; i < Mlg; i++)
if (aux & (1 << i))
sol = min(sol, parent[i][u].nd), u = parent[i][u].st;
return sol;
}
int main()
{
fi >> n >> m >> p;
for (int i = 2; i <= n; i++)
{
int u, v;
fi >> u >> v;
g[i].push_back(pii(u, v));
g[u].push_back(pii(i, v));
}
for (int i = 2; i < Mn; i++)
lg[i] = lg[i / 2] + 1;
depth[1] = 1;
dfs(1);
for (int i = 1; i < Mlg; i++)
{
for (int j = 1; j <= cnt - (1 << i) + 1; j++)
rmq[i][j] = min_depth(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
for (int j = 1; j <= n; j++)
{
parent[i][j].st = parent[i - 1][parent[i - 1][j].st].st;
parent[i][j].nd = min(parent[i - 1][j].nd, parent[i - 1][parent[i - 1][j].st].nd);
}
}
fi >> x >> y >> a >> b >> c >> d;
while (m--)
{
int anc = lca(x, y), ans = (x == y ? 0 : min(min_value(x, anc), min_value(y, anc)));
if (m < p)
fo << ans << "\n";
x = (x * a + y * b) % n + 1;
y = (y * c + ans * d) % n + 1;
}
return 0;
}