Pagini recente » Cod sursa (job #1347068) | Cod sursa (job #854095) | Cod sursa (job #1233418) | Cod sursa (job #1623503) | Cod sursa (job #2857718)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 32000;
const int lg = 15;
vector<vector<pair<int,int>>> dx(nmax+5);
int niv[nmax+5];
int up[nmax+5][lg+5], rmq[nmax+5][lg+5];
void dfs(int node, int ant) {
for(int i=1; i<=lg; i++)
up[node][i] = up[up[node][i-1]][i-1];
for(int i=1; i<=lg; i++)
rmq[node][i] = min(rmq[node][i-1], rmq[up[node][i-1]][i-1]);
for(auto i : dx[node]) {
if(i.first!=ant) {
niv[i.first] = niv[node] + 1;
up[i.first][0] = node;
rmq[i.first][0] = i.second;
dfs(i.first,node);
}
}
}
int query(int a, int b) {
if(niv[a] < niv[b]) swap(a,b);
int temp = 1e9;
for(int i=lg; i>=0; i--)
if(niv[up[a][i]]>=niv[b]) {
temp = min(temp, rmq[a][i]);
a = up[a][i];
}
if(a==b) return temp;
for(int i=lg; i>=0; i--) {
if(up[a][i]!=up[b][i]) {
temp = min(temp, rmq[a][i]);
temp = min(temp, rmq[b][i]);
a = up[a][i];
b = up[b][i];
}
}
temp = min(temp, rmq[a][0]);
temp = min(temp, rmq[b][0]);
return temp;
}
int main () {
ifstream f("atac.in");
ofstream g("atac.out");
int n,q,p; f >> n >> q >> p;
for(int x=2; x<=n; x++) {
int y,w; f >> y >> w;
dx[x].emplace_back(y,w);
dx[y].emplace_back(x,w);
}
niv[1] = 1;
dfs(1, 0);
int x,y,a,b,c,d,z; f >> x >> y >> a >> b >> c >> d;
vector<int> ans(q+5);
for(int i=1; i<=q; i++) {
if(x==y) z = 0;
else z = query(x,y);
ans[i] = z;
x = (x*a + y*a) % n + 1;
y = (y*c + z*d) % n + 1;
}
for(int i=q-p+1; i<=q; i++) g << ans[i] << "\n";
return 0;
}