Pagini recente » Cod sursa (job #974179) | Cod sursa (job #2415991) | Cod sursa (job #1598856) | Cod sursa (job #795795) | Cod sursa (job #1470038)
#include <fstream>
#include <vector>
using namespace std;
using pii = pair< int, int >;
#define mp make_pair
#define pb push_back
#define INF 2000000000
#define Nmax 32001
#define logN 15
ifstream fin("atac.in");
ofstream fout("atac.out");
struct {int vf, MIN;} str[logN][Nmax];
vector< pii > G[Nmax];
int h[Nmax];
void read(int) ;
void preprocess(int) ;
void DFS(int) ;
int query(int, int) ;
int main()
{
int m, n, p;
fin >> n >> m >> p;
read(n);
preprocess(n);
int x, y, z, a, b, c, d, X, Y;
fin >> x >> y >> a >> b >> c >> d;
for(; m; --m)
{
z = query(x, y);
if(m <= p) fout << z << '\n';
X = (x * a + y * b) % n + 1;
Y = (y * c + z * d) % n + 1;
x = X;
y = Y;
}
return 0;
}
void read(int n)
{
int vf, val;
for(int i = 2; i <= n; ++i)
{
fin >> vf >> val;
G[i].pb( mp(vf, val) );
G[vf].pb( mp(i, val) );
}
}
void preprocess(int n)
{
h[1] = 1;
DFS(1);
int i, d;
bool ok;
for(ok = 1, d = 1; ok; ++d)
for(ok = 0, i = 1; i <= n; ++i)
if(str[d - 1][ str[d - 1][i].vf ].vf > 0)
{
str[d][i].vf = str[d - 1][ str[d - 1][i].vf ].vf;
str[d][i].MIN = min(str[d - 1][i].MIN,
str[d - 1][ str[d - 1][i].vf ].MIN);
ok = 1;
}
}
void DFS(int vf)
{
for(auto it = G[vf].begin(); it != G[vf].end(); ++it)
if(h[it -> first] == 0)
{
h[it -> first] = 1 + h[vf];
str[0][it -> first].vf = vf;
str[0][it -> first].MIN = it -> second;
DFS(it -> first);
}
}
int query(int x, int y)
{
if(x == y) return 0;
if(h[x] > h[y]) swap(x, y);
int step, rez = INF;
if(h[x] != h[y])
for(step = logN - 1; step >= 0; --step)
if(str[step][y].vf > 0 && h[str[step][y].vf] >= h[x])
{
if(str[step][y].MIN < rez) rez = str[step][y].MIN;
y = str[step][y].vf;
}
if(x != y) // h[x] == h[y]
{
for(step = logN - 1; step >= 0; --step)
if(str[step][x].vf > 0 && str[step][x].vf != str[step][y].vf)
{
if(str[step][x].MIN < rez) rez = str[step][x].MIN;
if(str[step][y].MIN < rez) rez = str[step][y].MIN;
x = str[step][x].vf;
y = str[step][y].vf;
}
if(str[0][x].MIN < rez) rez = str[0][x].MIN;
if(str[0][y].MIN < rez) rez = str[0][y].MIN;
}
return rez;
}