Pagini recente » Cod sursa (job #3341036) | Cod sursa (job #1265793) | Cod sursa (job #2759891) | Cod sursa (job #1576276) | Cod sursa (job #1837496)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int Nmax = 32005;
int N, M, P, A, B, C, D, X, Y, LCA[25][Nmax], Log[Nmax], Use[Nmax], Level[Nmax], Dist[25][Nmax], dist, Sol[500005], nr;
vector < pair <int, int> > G[Nmax];
void Read()
{
fin>>N>>M>>P;
for(int i=2; i<=N; i++)
{
int U,V;
fin>>U>>V;
G[U].push_back(make_pair(i,V));
}
fin>>X>>Y>>A>>B>>C>>D;
}
void DFS(int nod)
{
Use[nod] = 1;
for(int i = 0; i < (int)G[nod].size(); i++)
{
int vecin = G[nod][i].first;
int cost = G[nod][i].second;
if(!Use[vecin])
{
Level[vecin] = Level[nod]+1;
LCA[0][vecin] = nod;
Dist[0][vecin] = cost;
DFS(vecin);
}
}
}
void Precalculate()
{
DFS(1);
for(int i = 2; i <= N; i++) Log[i] = Log[i/2]+1;
for(int i = 1; i <= Log[N]; i++)
for(int j = 1; j <= N; j++)
{
LCA[i][j] = LCA[i-1][LCA[i-1][j]];
Dist[i][j] = min(Dist[i-1][j], Dist[i-1][LCA[i-1][j]]);
}
}
int Stramos(int q, int p)
{
while(p)
{
int k = Log[p];
dist = min(dist, Dist[k][q]);
q = LCA[k][q];
p = p-(1<<k);
}
return q;
}
void Solve()
{
while(M--)
{
int xx = X, yy = Y;
dist = 10000000;
if(Level[X] < Level[Y]) swap(X,Y);
int da = Level[X] - Level[Y];
X=Stramos(X,da);
for(int i = Log[Level[X]]; i >= 0; i--)
{
if(LCA[i][X]!= LCA[i][Y])
{
dist = min(dist, min(Dist[i][X],Dist[i][Y]));
X= LCA[i][X];
Y= LCA[i][Y];
}
}
if(X!=Y) dist = min(dist, min(Dist[0][X], Dist[0][Y]));
if(dist == 10000000) dist = 0;
Sol[++nr] = dist;
X =(xx*A + yy*B)%N + 1;
Y =(yy*C + dist*D)%N + 1;
}
for(int i = nr-P+1; i <= nr; i++) fout<<Sol[i]<<'\n';
}
int main()
{
Read();
Precalculate();
Solve();
return 0;
}