Pagini recente » Cod sursa (job #656239) | Cod sursa (job #2286949) | Cod sursa (job #1740119) | Cod sursa (job #7666) | Cod sursa (job #2605557)
#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int N = 32001;
const int P2MAX = 15;
const int BIG = 1e9;
int ti[N], to[N];
vector <pair<int, int> > g[N];
int t[P2MAX][N], dp[P2MAX][N];
int timp;
void dfs(int node){
ti[node] = ++timp;
for(int p=0; p<(int)g[node].size(); p++){
int next = g[node][p].first;
int cost = g[node][p].second;
if(ti[next] == 0){
t[0][next] = node;
dp[0][next] = cost;
dfs(next);
}
}
to[node] = ++timp;
}
bool stramos(int x, int y){
return (ti[x] <= ti[y] && to[y] <= to[x]);
}
int lca(int x, int y){
if(stramos(x, y))
return x;
int pas = P2MAX - 1;
int s;
while(pas >= 0){
s = t[pas][x];
if(s != 0 && !stramos(s, y))
x = s;
pas--;
}
return t[0][x];
}
int solve(int x, int y){
int ans = BIG;
int pas = P2MAX - 1;
int s;
while(pas >= 0){
s = t[pas][x];
if(stramos(s, y)){
ans = min(ans, dp[pas][x]);
x = s;
}
pas--;
}
return ans;
}
int main()
{
int n,m,p,x,y,a,b,c,d,i,j,common,ans;
fin >> n >> m >> p;
for(i=2; i<=n; i++){
fin >> x >> y;
g[i].push_back(make_pair(x, y));
g[x].push_back(make_pair(i, y));
}
dfs(1);
for(i=1; (1<<i)<=n; i++)
for(j=1; j<=n; j++){
t[i][j] = t[i-1][t[i-1][j]];
dp[i][j] = min(dp[i-1][j], dp[i-1][t[i-1][j]]);
}
fin >> x >> y >> a >> b >> c >> d;
for(i=m; i>=1; i--){
common = lca(x, y);
ans = min(solve(x, common), solve(y, common));
if(i<=p)
fout << ans << "\n";
x = (x*a + y*b)%n + 1;
y = (y*c + ans*d)%n + 1;
}
return 0;
}