Pagini recente » Cod sursa (job #2709798) | Cod sursa (job #143738) | Cod sursa (job #13404) | Cod sursa (job #194715) | Cod sursa (job #3187773)
#include <fstream>
#include <vector>
#define INF 0x3FFFFFFF
#define sz 32000
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int n,m,q;
int A,B,C,D,X,Y;
vector <pair<int,int>> v[sz + 5];
int st[sz + 5];
int dr[sz + 5];
int p[16][sz + 5];
int val[16][sz + 5];
int o;
void dfs(int nod,int par,int mval)
{
p[0][nod]=par;
val[0][nod]=mval;
st[nod]=++o;
for(auto& i : v[nod])
if(i.second!=par)
dfs(i.second,nod,i.first);
dr[nod]=++o;
}
bool is_ancestor(int anc,int x)
{
return st[anc] <= st[x] && dr[x]<= dr[anc];
}
void proc()
{
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i<=n;i++)
p[j][i] = p[j-1][p[j-1][i]],val[j][i] = min(val[j-1][i],val[j-1][p[j-1][i]]);
}
int lca(int x,int y)
{
if(x==y)
return 0;
int sol = INF;
if(is_ancestor(x,y))
{
for(int i = 15;i>=0;i--)
if(!is_ancestor(p[i][y],x))
sol = min(sol,val[i][y]),y=p[i][y];
return min(sol,val[0][y]);
}
if(is_ancestor(y,x))
{
swap(x,y);
for(int i = 15;i>=0;i--)
if(!is_ancestor(p[i][y],x))
sol = min(sol,val[i][y]),y=p[i][y];
return min(sol,val[0][y]);
}
int xc = x;
for(int i =15;i>=0;i--)
{
int nod = p[i][xc];
if(!is_ancestor(nod,y))
xc=nod;
}
xc=p[0][xc];
for(int i =15;i>=0;i--){
if(!is_ancestor(p[i][x],xc))
sol=min(sol,val[i][x]),x=p[i][x];
if(!is_ancestor(p[i][y],xc))
sol=min(sol,val[i][y]),y=p[i][y];
}
sol=min(sol,val[0][x]);
sol=min(sol,val[0][y]);
return sol;
}
int main()
{
fin>>n>>m>>q;
for(int i=2;i<=n;i++)
{
int x,z;
fin>>x>>z;
v[x].push_back({z,i});
v[i].push_back({z,x});
}
fin>>X>>Y>>A>>B>>C>>D;
dfs(1,0,0);
dr[0]=++o;
proc();
for(int i =1 ; i<=m;i++)
{
int Z = lca(X,Y);
if(i>m-q)
fout<<Z<<'\n';
X=(X*A + Y*B)%n + 1;
Y=(Y*C + Z*D)%n + 1;
}
}