Pagini recente » Cod sursa (job #3310985) | Cod sursa (job #2832271) | Cod sursa (job #111483) | Cod sursa (job #565133) | Cod sursa (job #3304652)
#include <bits/stdc++.h>
#define cin ci
#define cout co
#define int long long
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
const int INF = 1e9;
const int Nmax = 32e3 + 1;
const int Lmax = 21;
int n, m, p, x, y, z, A ,B ,C , D;
int anc[Nmax][Lmax], mini[Nmax][Lmax], dist[Nmax];
vector<vector<pair<int, int>>> graf;
void binary()
{
for(int l=1; l<Lmax; l++)
for(int node=1; node<=n; node++)
{
anc[node][l] = anc[anc[node][l - 1]][l - 1];
mini[node][l] = min(mini[node][l - 1], mini[anc[node][l - 1]][l - 1]);
}
}
pair<int, int> findanc(int node, int nanc)
{
int ans = INF;
for(int l=0; l<Lmax; l++)
if(nanc & (1 << l))
{
ans = min(ans, mini[node][l]);
node = anc[node][l];
}
return {node, ans};
}
int lca(int node1, int node2)
{
int ans = INF;
if(dist[node1] < dist[node2])
swap(node1, node2);
pair<int, int> aux = findanc(node1, dist[node1] - dist[node2]);
ans = aux.second;
node1 = aux.first;
if(node1 == node2)
return ans;
for(int l=Lmax - 1; l>=0; l--)
if(anc[node1][l] != anc[node2][l])
{
ans = min({ans , mini[node1][l], mini[node2][l]});
node1 = anc[node1][l];
node2 = anc[node2][l];
}
return min({ans, mini[node1][0], mini[node2][0]});
}
void dfs(int node, int par)
{
dist[node] = dist[par] + 1;
anc[node][0] = par;
for(auto &[next, cost]:graf[node])
if(next != par)
{
mini[next][0] = cost;
dfs(next, node);
}
}
int32_t main()
{
cin >> n >> m >> p;
graf.assign(n+1, vector<pair<int, int>>());
for(int i=2; i<=n; i++)
{
cin >> x >> y;
graf[x].push_back({i, y});
graf[i].push_back({x, y});
}
dfs(1, 0);
mini[1][0] = INF;
binary();
cin >> x >> y >> A >> B >> C >> D;
for(int i=1; i<=m; i++)
{
int z = lca(x, y);
if(m - p < i)
cout << z << '\n';
x = (x * A + y * B) % n + 1;
y = (y * C + z * D) % n + 1;
}
return 0;
}