Pagini recente » Cod sursa (job #2489652) | Cod sursa (job #1789879) | Cod sursa (job #2518569) | Cod sursa (job #397176) | Cod sursa (job #369311)
Cod sursa(job #369311)
#include <fstream>
#include <vector>
using namespace std;
#define MAX_N 32005
#define MAX_L 20
#define MAX_P 10005
#define INF 0x3f3f3f3f
#define nod first
#define cst second
#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)
ifstream fin ("atac.in");
ofstream fout ("atac.out");
int N, M, P, T[MAX_L][MAX_N], D[MAX_L][MAX_N], L[MAX_N], Sol[MAX_P];
int X, Y, A, B, C, R;
vector <pair<int, int> > G[MAX_N];
void citire()
{
fin >> N >> M >> P;
for(int i = 2; i <= N; ++i)
{
int x, c;
fin >> x >> c;
G[x].push_back(make_pair(i, c));
G[i].push_back(make_pair(x, c));
}
fin >> X >> Y >> A >> B >> C >> R;
}
void dfs(int nod, int ant, int lev)
{
L[nod] = lev;
foreach(G[nod])
{
int act = it -> nod, cst = it -> cst;
if(act == ant) continue;
T[0][act] = nod;
D[0][act] = cst;
dfs(act, nod, lev+1);
}
}
void pre()
{
for(int k = 1; (1 << k) < N; ++k)
for(int i = 1; i <= N; ++i)
{
T[k][i] = T[k-1][T[k-1][i]];
D[k][i] = min(D[k-1][i], D[k-1][T[k-1][i]]);
}
}
int lca(int x, int y)
{
if(L[x] < L[y])
swap(x, y);
int log1, log2;
for(log1 = 1; (1 << log1) < L[x]; ++log1);
for(log2 = 1; (1 << log2) < L[y]; ++log2);
for(int k = log1; k >= 0; --k)
if(L[x] - (1 << k) >= L[y])
x = T[k][x];
if(x == y) return x;
for(int k = log2; k >= 0; --k)
if(T[k][x] != T[k][y])
x = T[k][x],
y = T[k][y];
return T[0][x];
}
int dist(int x, int y)
{
int sol(INF), log(1);
for(; (1 << log) < L[x]; ++log);
for(int k = log; k >= 0; --k)
if(L[x] - (1 << k) >= L[y])
sol = min(sol, D[k][x]),
x = T[k][x];
return sol;
}
void solve()
{
int Z(0);
for(int i = 1; i <= M; ++i)
{
int l = lca(X, Y);
if(X == Y)
Z = 0;
else
Z = min(dist(X, l), dist(Y, l));
// printf("%d %d %d\n", X, Y, Z);
if(i > M-P)
Sol[i-M+P] = Z;
X = ((X*A + Y*B) % N) + 1;
Y = ((Y*C + Z*R) % N) + 1;
}
for(int i = 1; i <= P; ++i)
fout << Sol[i] << "\n";
}
int main()
{
citire();
dfs(1, 0, 0);
pre();
solve();
}