Pagini recente » Cod sursa (job #722840) | Cod sursa (job #3208871) | Cod sursa (job #2107362) | Cod sursa (job #2562867) | Cod sursa (job #3322734)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("atac.in");
ofstream cout("atac.out");
const int NMAX = 32005;
int n,m,p,x,y,a,b,c,d,ans;
vector<int> G[NMAX];
int lg2[NMAX],niv[NMAX];
int anc[20][NMAX],dp[20][NMAX];
void dfs(int x,int tata,int h)
{
niv[x]=h;
for(auto y:G[x])
{
if(y==tata)
continue;
dfs(y,x,h+1);
}
}
int min_lant(int x,int y)
{
int ans=2e9;
if(niv[x]<niv[y])
swap(x,y);
int dif=niv[x]-niv[y];
for(int i=0;i<=18;i++)
if(dif&(1<<i))
{
ans=min(ans,dp[i][x]);
x=anc[i][x];
}
if(x==y) return ans;
for(int i=18;i>=0;i--)
{
if(anc[i][x]!=anc[i][y])
{
ans=min(ans,dp[i][x]);
ans=min(ans,dp[i][y]);
x=anc[i][x];
y=anc[i][y];
}
}
ans=min(ans,dp[0][x]);
ans=min(ans,dp[0][y]);
return ans;
}
int main()
{
cin>>n>>m>>p;
anc[0][1]=1;
dp[0][1]=2e9;
for(int i=2;i<=n;i++)
{
int y,v;
cin>>y>>v;
anc[0][i]=y;
dp[0][i]=v;
}
cin>>x>>y>>a>>b>>c>>d;
dfs(1,0,1);
for(int i=1;i<=18;i++)
for(int j=1;j<=n;j++)
{
anc[i][j]=anc[i-1][anc[i-1][j]];
dp[i][j]=min(dp[i-1][j],dp[i-1][anc[i-1][j]]);
}
for(int i=1;i<=m;i++)
{
ans=min_lant(x,y);
//cout<<x<<" "<<y<<" "<<ans<<"\n";
if(i>=m-p+1)
cout<<ans<<"\n";
x=(x*a+y*b)%n+1;
y=(y*c+ans*d)%n+1;
}
return 0;
}