Pagini recente » Cod sursa (job #388166) | Cod sursa (job #2803440) | Cod sursa (job #2292261) | Cod sursa (job #2397232) | Cod sursa (job #2632205)
#include <bits/stdc++.h>
#define DIM 35000
#define DIMM 500010
#define INF 2000000000
using namespace std;
int E[DIM*4],p[DIM*4],first[DIM],val[DIM],ans[DIMM],level[DIM];
int nr_chains,n,m,P,i,j,x,y,sol,k,cost,a,b,c,d;
int stramos[22][DIM],dp[22][DIM];
pair <int,int> rmq[22][DIM*4];
vector <pair<int,int> > L[DIM];
void dfs (int nod, int tata){
level[nod] = 1 + level[tata];
E[++k] = nod;
first[nod] = k;
for (auto it : L[nod]){
int vecin = it.first, cost = it.second;
if (vecin != tata){
stramos[0][vecin] = nod;
dp[0][vecin] = cost;
dfs (vecin,nod);
E[++k] = nod;
}}}
int get_lca (int x, int y){
int posx = first[x], posy = first[y];
if (posx > posy)
swap (posx,posy);
int nr = p[posy - posx + 1];
pair <int, int> sol = min (rmq[nr][posx], rmq[nr][posy - (1<<nr) + 1]);
return E[sol.second];
}
void query (int x, int y){
if (x == y)
return;
int lca = get_lca (x,y);
for (int i=17;i>=0;i--){
int nod = stramos[i][x];
if (level[nod] >= level[lca]){
sol = min (sol,dp[i][x]);
x = nod;
}}
for (int i=17;i>=0;i--){
int nod = stramos[i][y];
if (level[nod] >= level[lca]){
sol = min (sol,dp[i][y]);
y = nod;
}}}
int main (){
ifstream fin ("atac.in");
ofstream fout ("atac.out");
fin>>n>>m>>P;
for (i=2;i<=n;++i){
fin>>x>>cost;
L[i].push_back(make_pair(x,cost));
L[x].push_back(make_pair(i,cost));
}
dfs (1,0);
for (i=1;i<=k;++i){
rmq[0][i] = make_pair(level[E[i]],i);
if (i > 1)
p[i] = p[i/2] + 1;
}
for (i=1;(1<<i)<=k;++i)
for (j=1;j<=k;++j){
rmq[i][j] = rmq[i-1][j];
if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
}
for (i=1;(1<<i)<=n;++i){
for (j=1;j<=n;++j){
stramos[i][j] = stramos[i-1][stramos[i-1][j]];
dp[i][j] = min (dp[i-1][j],dp[i-1][stramos[i-1][j]]);
}
}
fin>>x>>y>>a>>b>>c>>d;
sol = INF;
query (x,y);
if (x == y)
sol = 0;
if (m == P)
fout<<sol<<"\n";
for (i=2;i<=m;++i){
x = (1LL * x * a + 1LL * y * b) % n + 1;
y = (1LL * y * c + 1LL * sol * d) % n + 1;
sol = INF;
query (x,y);
if (x == y)
sol = 0;
if (i >= m-P+1)
fout<<sol<<"\n";
}
return 0;
}