Pagini recente » Cod sursa (job #2932160) | Cod sursa (job #2979510) | Cod sursa (job #3293734) | Cod sursa (job #3241425) | Cod sursa (job #3272190)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
using VI = vector<int>;
using VVI = vector<VI>;
using VPI = vector<pair<int, int>>;
using VVPI = vector<VPI>;
ifstream fin("atac.in");
ofstream fout("atac.out");
VVPI G;
VVPI up;
VI v, niv;
int n, K, q, logaritm;
const int INF = (1 << 29);
void DFS(int x, int p)
{
if (x == 1)
v[x] = INF;
up[0][x].first = p;
up[0][x].second = v[x];
niv[x] = niv[p] + 1;
for (auto& y : G[x])
{
if (y.first == p)
continue;
v[y.first] = y.second;
DFS(y.first, x);
}
}
int LCA(int x, int y)
{
if (x == y)
return 0;
if (niv[x] > niv[y])
swap(x, y);
int mi = INF;
for (int i = logaritm; i >= 0; --i)
{
if (niv[up[i][y].first] >= niv[x])
{
mi = min(mi, up[i][y].second);
y = up[i][y].first;
}
}
for (int i = logaritm; i >= 0; --i)
{
if (up[i][y].first != up[i][x].first)
{
mi = min(mi, up[i][y].second);
mi = min(mi, up[i][x].second);
y = up[i][y].first;
x = up[i][x].first;
}
}
mi = min(mi, up[0][y].second);
mi = min(mi, up[0][x].second);
return mi;
}
int main()
{
fin >> n >> K >> q;
int x, cost;
G = VVPI(n + 1);
logaritm = ceil(log2(n));
up = VVPI(logaritm + 2, VPI(n + 1, make_pair(INF, INF)));
v = niv = VI(n + 1, -1);
for (int i = 1; i < n; ++i)
{
fin >> x >> cost;
G[i + 1].emplace_back(x, cost);
G[x].emplace_back(i + 1, cost);
}
DFS(1, 1);
for (int k = 1; k <= logaritm; ++k)
{
for (int i = 1; i <= n; ++i)
{
up[k][i].first = up[k - 1][up[k - 1][i].first].first;
up[k][i].second = min(up[k - 1][i].second, up[k - 1][up[k - 1][i].first].second);
}
}
int X, Y, A, B, C, D, Z = 0;
fin >> X >> Y >> A >> B >> C >> D;
for (int i = 1; i <= K; ++i)
{
if (i > 1)
{
X = (X * A + Y * B) % n + 1;
Y = (Y * C + Z * D) % n + 1;
}
Z = LCA(X, Y);
if (K - i + 1 <= q)
fout << Z << '\n';
}
}