Pagini recente » Cod sursa (job #1726653) | Cod sursa (job #1979781) | Cod sursa (job #2267287) | Cod sursa (job #2154651) | Cod sursa (job #1348768)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
typedef int var;
ifstream fin("atac.in");
ofstream fout("atac.out");
const var MAXN = 240002;
struct Edge {
var n, c;
Edge(var x, var y) {
n = x;
c = y;
}
};
vector<Edge> A[MAXN];
vector<var> EULER, DEPTH;
var B[MAXN], D[MAXN], PARENT[15][MAXN], MIN[15][MAXN];
var n, k, p;
void euler(var node) {
EULER.push_back(node);
DEPTH.push_back(D[node]);
B[node] = EULER.size() - 1;
for(vector<Edge>::iterator it = A[node].begin(); it != A[node].end(); ++it) {
Edge &e = *it;
if(e.n == PARENT[0][node]) continue;
PARENT[0][e.n] = node;
MIN[0][e.n] = e.c;
D[e.n] = D[node] + 1;
euler(e.n);
EULER.push_back(node);
DEPTH.push_back(D[node]);
}
}
var LOG[MAXN];
void build_log_table(var n) {
for(var i=2; i<=n; i++) {
LOG[i] = LOG[i/2] + 1;
}
}
void build_min_table() {
for(var i=1; (1<<i)<=n; i++) {
for(var j=1; j<=n; j++) {
PARENT[i][j] = PARENT[i-1][PARENT[i-1][j]];
MIN[i][j] = min(MIN[i-1][j], MIN[i-1][PARENT[i-1][j]]);
}
}
}
inline var zeros(var d) {
return d & (-d);
}
var find_min(var son, var parent) {
var d1 = D[son], d2 = D[parent];
var levels = d1 - d2;
var mmm = 10000001;
while(levels) {
var d = LOG[zeros(levels)];
mmm = min(mmm, MIN[d][son]);
son = PARENT[d][son];
levels -= zeros(levels);
}
return mmm;
}
var RMQ[15][MAXN], SOL[15][MAXN];
void build_table(var nm) {
for(var i=1; i<=nm; i++) {
RMQ[0][i] = DEPTH[i];
SOL[0][i] = EULER[i];
}
for(var i=1; (1<<i) <= nm; i++) {
for(var j=1; j+(1<<i)-1 <= nm; j++) {
if(RMQ[i-1][j] < RMQ[i-1][j+(1<<(i-1))]) {
RMQ[i][j] = RMQ[i-1][j];
SOL[i][j] = SOL[i-1][j];
} else {
RMQ[i][j] = RMQ[i-1][j+(1<<(i-1))];
SOL[i][j] = SOL[i-1][j+(1<<(i-1))];
}
}
}
}
var rmq(var b, var e) {
var len = LOG[e-b+1];
if(RMQ[len][b] < RMQ[len][e-(1<<len)+1]) {
return SOL[len][b];
} else {
return SOL[len][e-(1<<len)+1];
}
}
var lca(var n1, var n2) {
if(B[n1] < B[n2]) {
return rmq(B[n1], B[n2]);
} else {
return rmq(B[n2], B[n1]);
}
}
int main() {
var t, c;
fin>>n>>k>>p;
for(var i=2; i<=n; i++) {
fin>>t>>c;
A[t].push_back(Edge(i, c));
A[i].push_back(Edge(t, c));
//EDGES.push_back(FullEdge(i, t, c));
}
EULER.push_back(0);
DEPTH.push_back(0);
euler(1);
/*for(var i=0; i<EULER.size(); ++i) {
fout<<EULER[i]<<" ";
}
fout<<endl;
for(var i=0; i<EULER.size(); ++i) {
fout<<DEPTH[i]<<" ";
}
fout<<endl;
*/
build_log_table(EULER.size());
build_table(EULER.size() - 1);
build_min_table();
/*
for(var i=0; (1<<i) <= n; i++) {
for(var j=1; j<=n; j++) {
fout<<MIN[i][j]<<" ";
}
fout<<endl;
}
*/
var x, y, a, b, d;
fin>>x>>y>>a>>b>>c>>d;
for(var i=1; i<=k; i++) {
var lc = lca(x, y);
var rez = min(find_min(x, lc), find_min(y, lc));
x = (x*a + y*b)%n + 1;
y = (y*c + rez*d)%n + 1;
if(i > k-p) {
fout<<rez<<'\n';
}
}
return 0;
}