Pagini recente » Cod sursa (job #9065) | Cod sursa (job #2890497) | Cod sursa (job #29696) | Cod sursa (job #2838974) | Cod sursa (job #3186726)
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int LMAX = 17;
const int NMAX = 4e4+2;
int n,m,p,x,y,a,b,c,d,niv[NMAX],up[LMAX][NMAX],mn[LMAX][NMAX];
vector<pii> v[NMAX];
ifstream fin("atac.in");
ofstream fout("atac.out");
void minSelf(auto &a, auto b){
a = min(a, b);
}
void dfs(int nod, int tata = -1){
for(auto [fiu, cost]: v[nod]){
if(fiu == tata){
continue;
}
niv[fiu] = 1+niv[nod];
mn[0][fiu] = cost;
up[0][fiu] = nod;
for(int i = 1; i < LMAX; i++){
mn[i][fiu] = mn[i-1][fiu];
up[i][fiu] = up[i-1][up[i-1][fiu]];
minSelf(mn[i][fiu], mn[i-1][up[i-1][fiu]]);
}
dfs(fiu, nod);
}
}
pii kth(int x, int k){
int ans = LLONG_MAX;
for(int i = LMAX-1; i >= 0; i--){
if((k>>i)&1){
minSelf(ans, mn[i][x]);
x = up[i][x];
}
}
return {x, ans};
}
int query(int x, int y){
if(x == y){
return 0;
}
if(niv[x] > niv[y]){
swap(x, y);
}
int xcpy = x, ycpy = y;
int diff = niv[y]-niv[x];
y = kth(y, diff).first;
int lca = 0;
int ans = 0;
if(x != y){
for(int i = LMAX-1; i >= 0; i--){
if(up[i][x] != up[i][y]){
x = up[i][x];
y = up[i][y];
}
}
lca = up[0][x];
tie(x, y) = (pii){xcpy, ycpy};
ans = min(kth(x, niv[x]-niv[lca]).second, kth(y, niv[y]-niv[lca]).second);
}else{
lca = x;
tie(x, y) = (pii){xcpy, ycpy};
ans = kth(y, niv[y]-niv[lca]).second;
}
return ans;
}
signed main()
{
fin >> n >> m >> p;
for(int i = 2; i <= n; i++){
int u,val;
fin >> u >> val;
v[u].push_back({i, val});
v[i].push_back({u, val});
}
for(int i = 0; i < LMAX; i++){
for(int j = 0; j <= n; j++){
mn[i][j] = LLONG_MAX;
}
}
dfs(2);
fin >> x >> y >> a >> b >> c >> d;
for(int i = 1; i <= m; i++){
int z = query(x, y);
if(i >= m-p+1){
fout << z << "\n";
}
x = (x*a + y*b)%n + 1;
y = (y*c + z*c)%n + 1;
}
return 0;
}