Pagini recente » Cod sursa (job #389057) | Cod sursa (job #891515) | Cod sursa (job #3190026) | Cod sursa (job #98477) | Cod sursa (job #1938099)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int N,M,P,E[25][32005],Minedge[25][32005],Log[32005],Sol[500005],nr,X,Y,A,B,C,D,Level[32005],mine;
vector <pair <int,int> > G[32005];
void Read()
{
fin>>N>>M>>P;
for(int i=2;i<=N;i++)
{
int x,y;
fin>>x>>y;
G[x].push_back(make_pair(i,y));
}
fin>>X>>Y>>A>>B>>C>>D;
}
void DFS(int Nod)
{
for(int i = 0; i < (int)G[Nod].size(); ++i)
{
int Vecin = G[Nod][i].first;
int Cost = G[Nod][i].second;
E[0][Vecin]=Nod;
Minedge[0][Vecin]=Cost;
Level[Vecin] = Level[Nod] + 1;
DFS(Vecin);
}
}
void Precalculate()
{
DFS(1);
for(int i = 2; i <= N; ++i)
Log[i] = Log[i/2] + 1;
for(int i = 1; (1<<i) <= N; ++i)
{
for(int j = 1; j <= N; ++j)
{
E[i][j] = E[i-1][E[i-1][j]];
Minedge[i][j]=min(Minedge[i-1][j],Minedge[i-1][E[i-1][j]]);
}
}
}
int LCA(int x, int y)
{
if(Level[x] < Level[y])
swap(x,y);
while(Level[x]!=Level[y])
{
int K = Log[Level[x]-Level[y]];
x = E[K][x];
}
if(x == y)
return x;
for(int K = Log[Level[x]]; K >= 0 ; K--)
{
if(E[K][x] != E[K][y])
{
x = E[K][x];
y = E[K][y];
}
}
return E[0][x];
}
void findmin(int Nod,int stramos)
{
while(Nod!=stramos )
{
int a=Log[Level[Nod]-Level[stramos]];
mine=min(mine,Minedge[a][Nod]);
Nod=E[a][Nod];
}
}
void Solve()
{
while(M--)
{
mine=2000000000;
int x1=X,y1=Y;
if(X==Y)
{
mine=0;
}
else
{
int Nod=LCA(X,Y);
findmin(X,Nod);
findmin(Y,Nod);
}
Sol[++nr]=mine;
X =(x1*A + y1*B)%N + 1;
Y =(y1*C + mine*D)%N + 1;
}
for(int i = nr-P+1; i <= nr; i++) fout<<Sol[i]<<'\n';
}
int main()
{
Read();
Precalculate();
Solve();
return 0;
}