Pagini recente » Cod sursa (job #1872154) | Cod sursa (job #1421323) | Cod sursa (job #3307445) | Cod sursa (job #901240) | Cod sursa (job #3316398)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int Nmax=4e4+5,inf=1e7;
vector<pair<int,int>> g[Nmax];
int up[Nmax][20],dp[Nmax][20];
int tin[Nmax],tout[Nmax];
int timer=0;
void dfs(int nod,int pr,int val)
{
up[nod][0]=pr;
dp[nod][0]=val;
tin[nod]=++timer;
for(int i=1;i<=17;i++)
{
up[nod][i]=up[up[nod][i-1]][i-1];
dp[nod][i]=min(dp[nod][i-1],dp[up[nod][i-1]][i-1]);
}
for(auto [u,w]:g[nod])
{
if(u!=pr)
{
dfs(u,nod,w);
}
}
tout[nod]=timer;
}
bool upper(int a,int b)
{
return (tin[a]<=tin[b] && tout[b]<=tout[a]);
}
int lca(int x,int y)
{
if(upper(x,y)) return x;
if(upper(y,x)) return y;
for(int i=17;i>=0;i--)
{
if(!upper(up[x][i],y))
{
x=up[x][i];
}
}
return up[x][0];
}
int getans(int u,int x)
{
if(x==u) return inf;
int ans=inf;
for(int i=17;i>=0;i--)
{
if(!upper(up[x][i],u))
{
ans=min(ans,dp[x][i]);
x=up[x][i];
}
}
ans=min(ans,dp[x][0]);
return ans;
}
int main()
{
int n,m,p;
fin>>n>>m>>p;
for(int i=2;i<=n;i++)
{
int x,v;
fin>>x>>v;
g[i].push_back({x,v});
g[x].push_back({i,v});
}
dfs(1,1,inf);
deque<int> ans;
int x,y,a,b,c,d;
fin>>x>>y>>a>>b>>c>>d;
int l=lca(x,y);
int sol=0;
if(x!=y)
{
sol=min(getans(l,x),getans(l,y));
}
ans.push_back(sol);
m--;
while(m--)
{
x=(x*a+y*b)%n + 1;
y=(y*c+sol*d)%n +1;
sol=0;
l=lca(x,y);
if(x!=y)
{
sol=min(getans(l,x),getans(l,y));
}
ans.push_back(sol);
if(ans.size()>p) ans.pop_front();
}
while(!ans.empty())
{
fout<<ans.front()<<'\n';
ans.pop_front();
}
return 0;
}