Pagini recente » Cod sursa (job #1539102) | Cod sursa (job #1134186) | Cod sursa (job #2364166) | Cod sursa (job #2193186) | Cod sursa (job #1098974)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int NMAX = 32009;
const int INF = (1 << 30);
int N; int M; int P; int X; int Y; int A; int B; int C; int D;
int T[NMAX]; int Cost[NMAX]; bool see[NMAX];int lg[NMAX];int H[20][2 * NMAX];int C_min[20][2 * NMAX];
int Euler[NMAX * 2]; int Arb[4 * NMAX];int min_ind;int Level[2 * NMAX]; int Level_nod[NMAX];int rmq[20][NMAX * 2];
vector<pair <int, int> > G[NMAX];
int F[NMAX];
void read() {
fin >> N >> M >> P;
for(int i = 2; i <= N; ++i) {
int u, v;
fin >> u >> v;
G[i].push_back(make_pair(u, v));
G[u].push_back(make_pair(i, v));
}
fin >> X >> Y >> A >> B >> C >> D;
}
void dfs(int nod, int level) {
see[nod] = true; int cost;
Euler[++Euler[0]] = nod;
F[nod] = Euler[0];
Level[Euler[0]] = level;
Level_nod[nod] = level;
for(unsigned i = 0 ;i < G[nod].size(); ++i) {
if(see[G[nod][i].first] == false) {
T[G[nod][i].first] = nod;
Cost[G[nod][i].first] = G[nod][i].second;
dfs(G[nod][i].first, level + 1);
Euler[++Euler[0]] = nod;
Level[Euler[0]] = level;
}
}
}
void rmq_arbore() {
for(int i = 2; i <= Euler[0]; ++i)
lg[i] = lg[i/2] + 1;
for(int i = 0 ; i <= lg[N]; ++i)
for(int j = 1; j <= N; ++j)
C_min[i][j] = INF;
for(int i = 1; i <= N; ++i) {
H[0][i] = T[i];
C_min[0][i] = Cost[i];
}
for(int i = 1; i <= Euler[0]; ++i)
rmq[0][i] = i;
for(int i = 1; (1 << i) <= Euler[0]; ++i)
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 + (1 << (i - 1))]])
rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
}
for(int i = 1; i <= lg[N]; ++i)
for(int j = 1; j <= N; ++j) {
H[i][j] = H[i - 1][H[i - 1][j]];
C_min[i][j] = min(C_min[i - 1][j], C_min[i - 1][H[i - 1][j]]);
}
}
int query_cost(int X, int Y) {
int l1 = Level_nod[X]; int l2 = Level_nod[Y];
int min_value = (1 << 30);
while(l1 != l2) {
min_value = min(C_min[lg[l1 - l2]][X], min_value);
X = H[lg[l1 - l2]][X];
l1 = Level_nod[X];
//fout << l1 <<" " << l2 <<'\n';
}
return min_value;
}
int query(int st, int dr) {
int dif = dr - st + 1;
int lgg = lg[dif];
int l1 = 1 << lg[dif];
int sh = dif - l1;
int sol = rmq[lgg][st];
if(Level[sol] > Level[rmq[lgg][st + sh]])
sol = rmq[lgg][st + sh];
return Euler[sol];
}
int main() {
read();
dfs(1, 0);
rmq_arbore();
int LCA;
int Z; int min_cost;
if(X == Y) min_cost = 0 ;
else {
min_ind = 0;
LCA = query(min(F[X], F[Y]), max(F[Y], F[X]));
min_cost = min(query_cost(X, LCA), query_cost(Y, LCA));
}
X = (X * A + Y * B) % N + 1;
Y = (Y * C + min_cost * D) % N + 1;
for(int i = 2; i <= M; ++i) {
if(X == Y)
min_cost = 0;
else {
LCA = query(min(F[X], F[Y]), max(F[Y], F[X]));
min_cost = min(query_cost(X, LCA), query_cost(Y, LCA));
if(i >= M - P)
fout << min_cost <<'\n';
}
X = (X * A + Y * B) % N + 1;
Y = (Y * C + min_cost * D) % N + 1;
}
return 0;
}