Pagini recente » Cod sursa (job #317633) | Cod sursa (job #215065) | Cod sursa (job #2830369) | Cod sursa (job #360731) | Cod sursa (job #2776046)
#include <bits/stdc++.h>
#define LOG 19
#define DIM 32005
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int n, m, k, up[LOG + 1][DIM], mini[LOG + 1][DIM], depth[DIM];
int x, y, a, b, c, d;
bitset <DIM> v;
vector <pair <int, int>> edges[DIM];
vector <int> Q;
void dfs(int nod, int niv)
{
depth[nod] = niv;
v[nod] = 1;
for(auto child : edges[nod])
if(!v[child.first])
{
up[0][child.first] = nod;
mini[0][child.first] = child.second;
for(int i = 1; i <= LOG; i++)
{
up[i][child.first] = up[i - 1][up[i - 1][child.first]];
mini[i][child.first] = min(mini[i - 1][child.first], mini[i - 1][up[i - 1][child.first]]);
}
dfs(child.first, niv + 1);
}
}
int lca(int a, int b)
{
if(a == b)
return 0;
int ans = INT_MAX;
if(depth[a] < depth[b])
a = b;
int k = depth[a] - depth[b];
for(int i = LOG; i >= 0; i--)
if(k & (1 << i))
ans = min(ans, mini[i][a]), a = up[i][a];
if(a == b)
return ans;
for(int i = LOG; i >= 0; i--)
if(up[i][a] != up[i][b])
{
ans = min(ans, mini[i][a]);
ans = min(ans, mini[i][b]);
a = up[i][a];
b = up[i][b];
}
ans = min(ans, mini[0][a]);
ans = min(ans, mini[0][b]);
return ans;
}
int main()
{
f >> n >> m >> k;
const int MOD = n;
for(int i = 2; i <= n; i++)
{
int x, y;
f >> x >> y;
edges[i].push_back(make_pair(x, y));
edges[x].push_back(make_pair(i, y));
}
dfs(1, 0);
f >> x >> y >> a >> b >> c >> d;
for(int i = 1; i <= m; i++)
{
int p = lca(x, y);
Q.push_back(p);
x = (x * a + y * b) % n + 1;
y = (y * c + p * d) % n + 1;
}
for(int i = m - k; i < m; i++)
g << Q[i] << "\n";
return 0;
}