Pagini recente » Cod sursa (job #338388) | Cod sursa (job #2061228) | Cod sursa (job #38275) | Cod sursa (job #413511) | Cod sursa (job #3037623)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int NMAX=32010;
const int LOG=20;
vector<int> children[NMAX];
int n, m, p, x, y, a, b, c, d, up[NMAX][LOG], upmin[NMAX][LOG], depth[NMAX];
void dfs(int s){
for(auto u : children[s]){
depth[u]=depth[s]+1;
up[u][0]=s;
for(int j=1; j<LOG; j++){
up[u][j]=up[up[u][j-1]][j-1];
upmin[u][j]=min(upmin[u][j-1], upmin[up[u][j-1]][j-1]);
}
dfs(u);
}
}
int lca(int x, int y){
if(x==y) return 0;
int minbomb=INT_MAX;
if(depth[x]<depth[y]) swap(x, y);
int k=depth[x]-depth[y];
for(int j=LOG-1; j>=0; j--){
if(k & (1<<j)){
if(up[x][j]!=y) minbomb = min(minbomb, upmin[x][j]);
else{
int cx=x;
for(int wow=j-1; wow>=0; wow--){
minbomb=min(minbomb, (upmin[cx][wow]==0 ? INT_MAX : upmin[cx][wow]));
cx=up[cx][wow];
}
}
x=up[x][j];
}
}
if(x==y) return minbomb;
for(int j=LOG-1; j>=0; j--){
if(up[x][j]!=up[y][j]){
minbomb=min(minbomb, (upmin[x][j]==0 ? INT_MAX : upmin[x][j]));
minbomb=min(minbomb, (upmin[y][j]==0 ? INT_MAX : upmin[y][j]));
x=up[x][j];
y=up[y][j];
}
}
return min(minbomb, min(upmin[x][0], upmin[y][0]));
}
int main(){
fin >> n >> m >> p;
for(int i=2; i<=n; i++){
int x, y;
fin >> x >> y;
children[min(i, x)].push_back(max(i, x));
upmin[i][0]=y;
}
upmin[1][0]=INT_MAX;
up[1][0]=1;
fin >> x >> y >> a >> b >> c >> d;
dfs(1);
while(m--){
int minbomb = lca(x, y);
x=(x*a+y*b)%n+1;
y=(y*c+minbomb*d)%n+1;
if(m<p) fout << minbomb << '\n';
}
}