Pagini recente » Cod sursa (job #917109) | Cod sursa (job #3353021) | Cod sursa (job #1102556) | Cod sursa (job #1412054) | Cod sursa (job #2085854)
#include <bits/stdc++.h>
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int n,q,t,a,b,x,y,poz,nr,i,j,k,c,d,A,B,z,m,p,L[1<<15];
int P[1<<15],put[1<<17],rmq[17][1<<18],V[17][1<<18],T[17][1<<18];
bool viz[1<<15];
vector<pair<int,int>>G[1<<15];
void dfs(int x,int level)
{
for(int i=1;i<=15;++i)
{
T[i][x]=T[i-1][T[i-1][x]];
V[i][x]=min(V[i-1][x],V[i-1][T[i-1][x]]);
}
viz[x]=1;
L[x]=level;
rmq[0][++nr]=x;
P[x]=nr;
for(int i=0;i<G[x].size();++i)
if(!viz[G[x][i].first])
{
V[0][G[x][i].first]=G[x][i].second;
T[0][G[x][i].first]=x;
dfs(G[x][i].first,level+1);
rmq[0][++nr]=x;
}
}
void build_rmq()
{
put[1]=0;
for(i=2;i<=nr;i++)
put[i]=put[i/2]+1;
for(i=1;(1<<i)<=nr;++i)
for(j=1,k=1<<(i-1);j<=nr;++j)
if(L[rmq[i-1][j]]<L[rmq[i-1][j+k]])
rmq[i][j]=rmq[i-1][j];
else
rmq[i-1][j+k];
}
int LCA(int x,int y)
{
if(P[x]>P[y])
swap(x,y);
int d=put[P[y]-P[x]];
int nod=rmq[d][P[y]-(1<<d)+1];
if(L[nod]>L[rmq[d][P[x]]])
nod=rmq[d][P[x]];
return nod;
}
int query(int x,int y)
{
if(x==y)
return 1<<30;
int dist=L[y]-L[x],sol=1<<30;
for(int i=15;i>=0;--i)
if(dist&(1<<i))
{
sol=min(sol,V[i][y]);
y=T[i][y];
dist-=(1<<i);
}
return sol;
}
int main()
{
f>>n>>m>>p;
for(i=2;i<=n;++i)
{
f>>x>>y;
G[x].push_back(make_pair(i,y));
G[i].push_back(make_pair(x,y));
}
dfs(1,1);
build_rmq();
f>>x>>y>>a>>b>>c>>d;
for(i=1;i<=m;++i)
{
if(x!=y)
{
int rad=LCA(x,y);
z=min(query(rad,x),query(rad,y));
}
else
z=0;
if(i>=m-p+1)
g<<z<<'\n';
x=(x*a+y*b)%n+1;
y=(y*c+z*d)%n+1;
}
return 0;
}