Pagini recente » Cod sursa (job #1001094) | Cod sursa (job #1664840) | Cod sursa (job #63766) | Cod sursa (job #1490448) | Cod sursa (job #2351982)
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair< int , int > PII;
class RMQ {
private:
vector < int > logVec;
vector < vector < int > > rmqVec;
public:
RMQ(vector < int > _RMQ){
logVec.assign(_RMQ.size() + 1, 0);
for (int i = 2; i < logVec.size(); i++) {
logVec[i] = logVec[i / 2] + 1;
}
rmqVec.assign(logVec.back() + 1, vector < int >(_RMQ.size()));
rmqVec[0] = _RMQ;
for (int logX = 1; logX < rmqVec.size(); logX++) {
for (int i = 0; i + (1 << logX) <= _RMQ.size(); i++) {
rmqVec[logX][i] = min(rmqVec[logX - 1][i], rmqVec[logX - 1][i + (1 << (logX - 1))]);
}
}
}
int getMin(int l, int r) { // ! returns the answer for the interval [l, r) !
int logX = logVec[r - l];
return min(rmqVec[logX][l], rmqVec[logX][r - (1 << logX)]);
}
};
int n, m, p, k, a, b, c, d, x, y, dp[16][1 << 15], lvl[1 << 15], mn[16][1 << 15];
vector < int > bck;
vector < int > fst;
vector < int > euler;
vector < PII > V[1 << 15];
void eulerTour(int curr, int dad, int l) {
lvl[curr] = l;
int newIndex = bck.size();
bck.push_back(curr);
fst[curr] = euler.size();
euler.push_back(newIndex);
for (int i = 1; i <= 15; i++) {
dp[i][curr] = dp[i - 1][dp[i - 1][curr]];
mn[i][curr] = min(mn[i - 1][curr], mn[i - 1][dp[i - 1][curr]]);
}
for (auto it : V[curr]) {
if (it.first == dad) continue;
eulerTour(it.first, curr, l + 1);
euler.push_back(newIndex);
}
}
int main(){
ifstream cin("atac.in");
ofstream cout("atac.out");
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> p;
for (int i = 1; i <= 15; i++) {
for (int j = 1; j <= n; j++) {
mn[i][j] = INT_MAX;
}
}
for (int i = 1, x, y; i < n; i++) {
cin >> x >> y;
V[x].push_back({i + 1, y});
mn[0][i + 1] = y;
dp[0][i + 1] = x;
}
cin >> x >> y >> a >> b >> c >> d;
fst.assign(n + 1, -1);
eulerTour(1, 1, 1);
RMQ rmq(euler);
int ans;
for (int i = 1; i <= m; i++) {
int nodeX = fst[x], nodeY = fst[y];
if (nodeX > nodeY) swap(nodeX, nodeY);
int cpx = x, cpy = y;
if (nodeX == nodeY) {
ans = 0;
x = (cpx * a + cpy * b) % n + 1;
y = (cpy * c + ans * d) % n + 1;
if (m - i + 1 <= p)
cout << ans << "\n";
continue;
}
int newIndex = rmq.getMin(nodeX, nodeY + 1);
int oldIndex = bck[newIndex];
ans = INT_MAX;
int diff = lvl[x] - lvl[oldIndex];
while (diff) {
int lg = log2(diff);
ans = min(ans, mn[lg][x]);
x = dp[lg][x];
diff -= (1 << lg);
}
diff = lvl[y] - lvl[oldIndex];
while (diff) {
int lg = log2(diff);
ans = min(ans, mn[lg][y]);
y = dp[lg][y];
diff -= (1 << lg);
}
x = (cpx * a + cpy * b) % n + 1;
y = (cpy * c + ans * d) % n + 1;
if (m - i + 1 <= p)
cout << ans << "\n";
}
return 0;
}