Pagini recente » Cod sursa (job #10396) | Cod sursa (job #3171614)
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 32000
struct Node
{
int ancestor, minCost;
};
int n, m, p, L, timer;
vector <int> tin, tout, height;
vector <vector <pair <int, int> > > graph;
vector <vector <Node> > dp;
bitset <MAX_N + 1> viz;
void dfs(int node, int parent, int edgeCost, int h)
{
viz[node] = 1;
tin[node] = ++timer;
height[node] = h;
dp[0][node].minCost = edgeCost;
dp[0][node].ancestor = parent;
for(int i = 1; i <= L; i ++)
{
dp[i][node].ancestor = dp[i - 1][dp[i - 1][node].ancestor].ancestor;
dp[i][node].minCost = min(dp[i - 1][node].minCost, dp[i - 1][dp[i - 1][node].ancestor].minCost);
}
for(pair <int, int> neighbour : graph[node])
if(!viz[neighbour.first])
dfs(neighbour.first, node, neighbour.second, h + 1);
tout[node] = ++timer;
}
bool isAncestor(int a, int b)
{
return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}
int lca(int a, int b)
{
if(isAncestor(a, b))
return a;
if(isAncestor(b, a))
return b;
for(int i = L; i >= 0; i --)
{
if(!isAncestor(dp[i][a].ancestor,b))
a = dp[i][a].ancestor;
}
return dp[0][a].ancestor;
}
int solve(int firstNode, int secondNode)
{
int centru = lca(firstNode, secondNode);
// cout << centru << "\n";
int ans = INT_MAX;
// cout << firstNode << " " << secondNode << "\n";
for(int i = L; i >= 0; i --)
{
// cout << "ancestor " <<dp[i][firstNode].ancestor << "\n";
if(height[dp[i][firstNode].ancestor] >= height[centru])
{
// cout << dp[i][firstNode].ancestor << " " << height[dp[i][firstNode].ancestor] << " " << height[centru] << " " << dp[i][firstNode].minCost << "\n";
ans = min(ans, dp[i][firstNode].minCost);
firstNode = dp[i][firstNode].ancestor;
}
if(height[dp[i][secondNode].ancestor] >= height[centru])
{
ans = min(ans, dp[i][secondNode].minCost);
secondNode = dp[i][secondNode].ancestor;
}
}
return ans;
}
int main()
{
ios_base :: sync_with_stdio(0);
cin.tie(0);
freopen("atac.in", "r", stdin);
freopen("atac.out", "w", stdout);
cin >> n >> m >> p;
graph.resize(n + 1);
for(int i = 2; i <= n; i++)
{
int a, b;
cin >> a >> b;
graph[i].push_back({a, b});
graph[a].push_back({i, b});
}
// for(int i = 1; i <= n; i ++)
// {
// cout << i << "\n";
// for(auto neighbour : graph[i])
// cout << i << " " << neighbour.first << " " << neighbour.second << "\n";
// cout << "\n";
// }
int x, y, a, b, c, d, z;
cin >> x >> y >> a >> b >> c >> d;
L = log2(n);
tin.resize(n + 1);
tout.resize(n + 1);
height.resize(n + 1);
dp.resize(L + 1, vector <Node> (n + 1));
dfs(1, 1, INT_MAX, 1);
for(int i = 1; i <= m - p; i ++)
{
z = solve(x, y);
// cout << z << "\n";
// cout << "end solve \n";
int copyX = x, copyY = y;
x = (copyX * a + copyY * b) % n + 1; //intra in int
y = (copyY * c + z * d) % n + 1;
}
for(int i = m - p + 1; i <= m; i ++)
{
// cout << x << " " << y << "\n";
z = solve(x, y);
cout << z << "\n";
// cout << "end solve \n";
int copyX = x, copyY = y;
x = (copyX * a + copyY * b) % n + 1; //intra in int
y = (copyY * c + z * d) % n + 1;
// cout << "\n";
}
return 0;
}