Pagini recente » Cod sursa (job #1969186) | Cod sursa (job #278400) | Cod sursa (job #665408) | Cod sursa (job #3124065) | Cod sursa (job #1106701)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("atac.in");
ofstream fout ("atac.out");
const int NMAX = 32109;
int N; int M; int X; int Y; int A; int B; int C2; int D;int P;
int euler[NMAX * 2]; int level[NMAX * 2]; bool see[NMAX]; int first[NMAX];int T[NMAX];
int rmq[17][NMAX * 2]; int C[17][NMAX]; int TT[17][NMAX];int lg[NMAX * 2];
int l[NMAX];
vector<pair <int, int> > G[NMAX];
void read() {
fin >> N >> M >> P;
for(int i = 2; i <= N; ++i) {
int x, cost;
fin >> x >> cost;
G[x].push_back(make_pair(i, cost));
G[i].push_back(make_pair(x, cost));
}
fin >> X >> Y >> A >> B >> C2 >> D;
}
void dfs(int nod, int lev) {
see[nod] = true;
euler[++euler[0]] = nod;
level[++level[0]] = lev;
first[nod] = euler[0];
l[nod] = lev;
for(unsigned i = 0 ;i < G[nod].size(); ++i)
if(see[G[nod][i].first] == false) {
dfs(G[nod][i].first, lev + 1);
euler[++euler[0]] = nod;
level[++level[0]] = lev;
T[G[nod][i].first] = nod;
C[0][G[nod][i].first] = G[nod][i].second;
}
}
void smen() {
for(int i = 2; i <= euler[0]; ++i)
lg[i] = lg[i / 2] + 1;
for(int i = 1; i <= N; ++i)
TT[0][i] = T[i];
for(int i = 1; (1 << i) <= N; ++i)
for(int j = 1; j <= N; ++j) {
TT[i][j] = TT[i - 1][TT[i - 1][j]];
C[i][j] = min(C[i - 1][j], C[i - 1][TT[i - 1][j]]);
}
}
void RMQ() {
for(int i = 1; i <= euler[0]; ++i)
rmq[0][i] = i;
for(int i = 1; (1 << i) <= euler[0]; ++i) {
int l = 1 << (i - 1);
for(int j = 1; j <= euler[0] - (1 << i) + 1; ++j) {
rmq[i][j] = rmq[i - 1][j];
if(level[rmq[i][j]] > level[rmq[i - 1][j + l]])
rmq[i][j] = rmq[i - 1][j + l];
}
}
}
int LCA(int x, int y) {
int st = first[x]; int dr = first[y];
if(st > dr) swap(st, dr);
int dif = dr - st + 1;
int lgg = lg[dif];
int bucket = (1 << lg[dif]);
int answ = rmq[lgg][st];
if(level[answ] > level[rmq[lgg][st + dif - bucket]])
answ = rmq[lgg][st + dif - bucket];
return euler[answ];
}
int findm(int X, int Y) {
int sol = (1 << 30);int l1 = l[X]; int l2 = l[Y];
while(l1 > l2) {
int dif = l1 - l2;
sol = min(sol, C[lg[dif]][X]);
X = TT[lg[dif]][X];
l1 = l[X];
}
return sol;
}
void solve() {
dfs(1, 0);
smen();
RMQ();
for(int i = 1; i <= M; ++i) {
int lca = LCA(X, Y);
int find_cost = min(findm(X, lca) , findm(Y, lca));
if(i > M - P) fout << find_cost <<'\n';
X = (X * A + Y * B) % N + 1;
Y = (Y * C2 + find_cost * D) % N + 1;
}
}
int main() {
read();
solve();
return 0;
}