Pagini recente » Cod sursa (job #562656) | Cod sursa (job #458878) | Cod sursa (job #1408654) | Cod sursa (job #2902096) | Cod sursa (job #2329747)
#include<bits/stdc++.h>
#define N 32005
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n, e;
int LOG[2*N], F[N], L[2*N], E[2*N];
int viz[2*N];
int dp[N][20], mn[N][20];
int rmq[N][20];
vector<pii>V[N];
int m,p;
void DFS(int x, int h) {
E[++e]=x;
L[e]=h;
F[x]=e;
viz[x]=1;
for (auto it:V[x]) {
if (!viz[it.fi]) {
DFS(it.fi, h+1);
dp[it.fi][0]=x;
mn[it.fi][0]=it.se;
L[++e]=h;
E[e]=x;
}
}
}
int rs;
int LCA(int a, int b) {
a=F[a], b=F[b];
if (a>b) swap(a,b);
int k=LOG[b-a+1];
if (L[rmq[a][k]]<L[rmq[b-(1<<k)+1][k]]) return E[rmq[a][k]];
else return E[rmq[b-(1<<k)+1][k]];
}
int solve(int x, int p) {
int k=L[F[x]]-L[F[p]];
int nod=x, rs=1e9;
for (int i=0; i<=16; ++i) {
if ((1<<i) & k) {
rs=min(rs, mn[nod][i]);
nod=dp[nod][i];
}
}
return rs;
}
int main() {
ifstream cin("atac.in");
ofstream cout("atac.out");
cin>>n>>m>>p;
for (int i=2; i<=n; ++i) {
int x,y; cin>>x>>y;
V[x].push_back({i,y});
V[i].push_back({x,y});
}
for (int i=2; i<=2*N-5; ++i) LOG[i]=LOG[i>>1]+1;
DFS(1,0);
for (int i=1; i<=e; ++i) rmq[i][0]=i;
for (int j=1; (1<<j)<=e; ++j) {
for (int i=1; i+(1<<j)-1<=e; ++i) {
if (L[rmq[i][j-1]]<L[rmq[i+(1<<(j-1))][j-1]]) rmq[i][j]=rmq[i][j-1];
else rmq[i][j]=rmq[i+(1<<(j-1))][j-1];
}
}
for (int j=1; (1<<j)<=n; ++j) {
for (int i=1; i<=n; ++i) {
dp[i][j]=dp[dp[i][j-1]][j-1];
mn[i][j]=min(mn[i][j-1], mn[dp[i][j-1]][j-1]);
}
}
int X,Y,A,B,C,D,Z;
cin>>X>>Y>>A>>B>>C>>D;
for (int i=1; i<=m; ++i) {
int lca=LCA(X,Y);
if (X==Y) rs=0;
else rs=min(solve(X, lca), solve(Y, lca));
Z=rs;
X=(X*A+Y*B)%n+1;
Y=(Y*C+Z*D)%n+1;
if (m-i+1<=p) cout<<rs<<'\n';
}
return 0;
}