Pagini recente » Cod sursa (job #3299593) | Cod sursa (job #3298298) | Cod sursa (job #3299778) | Cod sursa (job #3272555) | Cod sursa (job #3299583)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int NMAX = 32001, LOG = 16, INF = INT_MAX;
int n, m, p, up[NMAX][LOG], depth[NMAX], min_edge[NMAX][LOG];
vector<pair<int, int>> adj[NMAX];
void dfs(int node, int parent, int cost)
{
up[node][0] = parent;
min_edge[node][0] = cost;
depth[node] = depth[parent] + 1;
for(pair<int, int> child : adj[node])
if(child.first != parent)
dfs(child.first, node, child.second);
}
void precalculare()
{
for(int k = 1; k < LOG; k++)
{
for(int node = 1; node <= n; node++)
{
up[node][k] = up[up[node][k - 1]][k - 1];
min_edge[node][k] = min(min_edge[node][k - 1], min_edge[up[node][k - 1]][k - 1]);
}
}
}
int lca(int u, int v)
{
if(u == v)
return 0;
if(depth[u] < depth[v])
swap(u, v);
int ans = INF;
for(int k = LOG - 1; k >= 0; k--)
{
if(depth[up[u][k]] >= depth[v])
{
ans = min(ans, min_edge[u][k]);
u = up[u][k];
}
}
if(u == v)
return ans;
for(int k = LOG - 1; k >= 0; k--)
{
if(up[u][k] != up[v][k])
{
ans = min({ans, min_edge[u][k], min_edge[v][k]});
u = up[u][k];
v = up[v][k];
}
}
return min({ans, min_edge[u][0], min_edge[v][0]});
}
int main()
{
fin >> n >> m >> p;
for(int i = 2; i <= n; i++)
{
int u, v;
fin >> u >> v;
adj[u].emplace_back(i, v);
adj[i].emplace_back(u, v);
}
dfs(1, 0, INF);
precalculare();
int x, y, A, B, C, D;
fin >> x >> y >> A >> B >> C >> D;
for(int i = 1; i <= m; i++)
{
int z = lca(x, y);
if(i > m - p)
fout << z << "\n";
x = (x * A + y * B) % n + 1;
y = (y * C + z * D) % n + 1;
}
fin.close();
fout.close();
return 0;
}