Pagini recente » Rating Eduard Socea (edawrds94) | Cod sursa (job #2655488) | Profil yawninghorse | Cod sursa (job #376440) | Cod sursa (job #3272214)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
using VI = vector<ll>;
using VVI = vector<VI>;
using VPI = vector<pair<ll, ll>>;
using VVPI = vector<VPI>;
ifstream fin("atac.in");
ofstream fout("atac.out");
VVPI G;
VVPI up;
VI v, niv;
ll n, K, q, logaritm;
const ll INF = (1 << 29);
void DFS(ll x, ll 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);
}
}
ll LCA(ll x, ll y)
{
if (x == y)
return 0;
if (niv[x] > niv[y])
swap(x, y);
ll mi = INF;
for (ll 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;
}
}
if (x == y)
return mi;
for (ll 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;
ll 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, INF);
for (ll 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 (ll k = 1; k <= logaritm; ++k)
{
for (ll 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);
}
}
ll X, Y, A, B, C, D, Z = 0;
fin >> X >> Y >> A >> B >> C >> D;
VI last;
for (ll 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';
}
/*
reverse(last.begin(), last.end());
for (auto x : last)
fout << x << '\n';
*/
fin.close();
fout.close();
}