Pagini recente » Cod sursa (job #2755943) | Cod sursa (job #2474566) | Cod sursa (job #1685848) | Cod sursa (job #436479) | Cod sursa (job #1685836)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("atac.in");
ofstream g("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[Nmax], nr;
vector < pair <int, int> > G[Nmax];
void Read()
{
f>>n>>m>>p;
for(int i = 2; i <= n; i++)
{
int u,v;
f>>u>>v;
G[u].push_back(make_pair(i,v));
G[i].push_back(make_pair(u,v));
}
f>>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);
}
}
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];
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++) g<<Sol[i]<<'\n';
}
int main()
{
Read();
Precalculate();
Solve();
return 0;
}