Pagini recente » Cod sursa (job #2462140) | Cod sursa (job #1568026) | Cod sursa (job #3178361) | Cod sursa (job #2929117) | Cod sursa (job #2633937)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("atac.in");
ofstream cout ("atac.out");
int n, m, p, x, y, a, b, c, d;
vector <pair <int, int>> g[32005];
int t[16][32005], mn[16][32005], h[32005];
void dfs(int nod) {
for(auto &i : g[nod]) {
int fiu = i.first, cost = i.second;
if(!t[0][fiu]) {
t[0][fiu] = nod;
mn[0][fiu] = cost;
h[fiu] = h[nod] + 1;
dfs(fiu);
}
}
}
int tata(int nod, int x) {
int p = 1, cnt = 0;
while(x) {
if(p & x)
nod = t[cnt][nod], x ^= p;
p <<= 1;
cnt++;
}
return nod;
}
int lca(int x, int y) {
int st = 0, dr = min(h[x], h[y]), mid;
while(st <= dr) {
mid = (st + dr) >> 1;
if(tata(x, h[x] - mid) == tata(y, h[y] - mid))
st = mid + 1;
else
dr = mid - 1;
}
return tata(x, h[x] - dr);
}
int getMin(int nod, int x) {
int ans = 100005, p = 1, cnt = 0;
while(x) {
if(p & x) {
ans = min(ans, mn[cnt][nod]);
nod = t[cnt][nod];
x ^= p;
}
p <<= 1;
cnt++;
}
return ans;
}
int solve(int x, int y) {
if(x == y)
return 0;
int nod = lca(x, y);
return min(getMin(x, h[x] - h[nod]), getMin(y, h[y] - h[nod]));
}
int main() {
cin >> n >> m >> p;
for(int i = 2; i <= n; i++) {
cin >> x >> y;
g[i].push_back({x, y});
g[x].push_back({i, y});
}
dfs(1);
for(int i = 1; i <= 15; i++) {
for(int j = 1; j <= n; j++) {
t[i][j] = t[i - 1][t[i - 1][j]];
mn[i][j] = min(mn[i - 1][j], mn[i - 1][t[i - 1][j]]);
}
}
cin >> x >> y >> a >> b >> c >> d;
for(; m; m--) {
int z = solve(x, y);
if(m <= p)
cout << z << "\n";
x = (x * a + y * b) % n + 1;
y = (y * c + z * d) % n + 1;
}
return 0;
}