Pagini recente » Cod sursa (job #1206452) | Cod sursa (job #312707) | Cod sursa (job #1535877) | Cod sursa (job #499089) | Cod sursa (job #2436103)
#include <bits/stdc++.h>
using namespace std;
ifstream in("atac.in");
ofstream out("atac.out");
const int N = 1e5+5;
const int L = 20;
vector<pair<int,int> >v[N];
int lvl[N],dp[L][N],cost[L][N];
void dfs(int x)
{
for (auto it: v[x])
if (!lvl[it.first])
{
lvl[it.first] = 1+lvl[x];
dp[0][it.first] = x;
cost[0][it.first] = it.second;
dfs(it.first);
}
}
int query(int x, int y)
{
if (lvl[x]<lvl[y])
swap(x,y);
int L1 = 1, L2 = 1;
while ((1<<L1)<lvl[x])
L1++;
while ((1<<L2)<lvl[y])
L2++;
int ans = INT_MAX;
for (int i = L1; i>=0; i--)
if (lvl[x]-(1<<i)>=lvl[y])
{
ans = min(ans,cost[i][x]);
x = dp[i][x];
}
if (x == y)
return ans;
for (int i = L2; i>=0; i--)
if (lvl[x]-(1<<i)>=0 && dp[i][x]!=dp[i][y])
{
ans = min(ans,min(cost[i][x],cost[i][y]));
x = dp[i][x];
y = dp[i][y];
}
ans = min(ans,min(cost[0][x],cost[0][y]));
return ans;
}
int main()
{
int n,m,p;
in >> n >> m >> p;
for (int i = 2; i<=n; i++)
{
int x,y;
in >> x >> y;
v[x].push_back({i,y});
v[i].push_back({x,y});
}
int x,y,a,b,c,d;
in >> x >> y >> a >> b >> c >> d;
lvl[1] = 1;
dfs(1);
for (int i = 1; (1<<i)<=n; i++)
for (int j = 1; j<=n; j++)
{
dp[i][j] = dp[i-1][dp[i-1][j]];
cost[i][j] = min(cost[i-1][j],cost[i-1][dp[i-1][j]]);
}
for (int i = 1; i<=m; i++)
{
int z = query(x,y);
if (i>=m-p+1)
out << z << "\n";
x = (x*a+y*b)%n+1;
y = (y*c+z*d)%n+1;
}
}