Pagini recente » Cod sursa (job #2719262) | Cod sursa (job #432033) | Cod sursa (job #1951262) | Cod sursa (job #44249) | Cod sursa (job #2769229)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int nmax = 32005;
int n, m, p, dp[nmax][15][2], lev[nmax], x, y, a, b, c, d;
vector <pair <int, int> > G[nmax];
void dfs(int nod, int tata, int nivel){
lev[nod] = nivel;
for (auto it : G[nod]){
if (it.first == tata){
continue;
}
dp[it.first][0][0] = nod;
dp[it.first][0][1] = it.second;
dfs(it.first, nod, nivel + 1);
}
}
int lca(int x, int y){
if (lev[x] < lev[y]) swap(x, y);
int minim = 1e9;
if (lev[x] != lev[y]){
for (int i = 14; i >= 0; --i){
if (lev[x] - (1 << i) >= lev[y]){
x = dp[x][i][0];
minim = min(minim, dp[x][i][1]);
}
}
}
if (x == y){
return minim;
}
for (int i = 14; i >= 0; --i){
if (dp[x][i][0] != 0 && dp[y][i][0] != 0 && dp[x][i][0] != dp[y][i][0]){
x = dp[x][i][0];
y = dp[y][i][0];
minim = min(minim, dp[x][i][1]);
minim = min(minim, dp[y][i][1]);
}
}
minim = min(minim, dp[x][0][1]);
minim = min(minim, dp[y][0][1]);
return minim;
}
int main(){
fin >> n >> m >> p;
for (int i = 2; i <= n; ++i){
int u, v;
fin >> u >> v;
G[u].push_back({i, v});
G[i].push_back({u, v});
}
dfs(1, 0, 0);
for (int i = 1; (1 << i) <= n; ++i){
for (int j = 1; j <= n; ++j){
dp[j][i][0] = dp[dp[j][i - 1][0]][i - 1][0];
dp[j][i][1] = min(dp[j][i - 1][1], dp[dp[j][i - 1][0]][i - 1][1]);
}
}
fin >> x >> y >> a >> b >> c >> d;
for (int i = 1; i <= m; ++i){
int val = lca(x, y);
if (x == y){
val = 0;
}
if (i > m - p){
fout << val << "\n";
}
x = (1LL * x * a + 1LL * y * b) % n + 1;
y = (1LL * y * c + 1LL * val * d) % n + 1;
}
fin.close();
fout.close();
return 0;
}