Pagini recente » Cod sursa (job #33599) | Cod sursa (job #2593419) | Cod sursa (job #2744640) | Cod sursa (job #997528) | Cod sursa (job #1524912)
#include<fstream>
#include<vector>
#include<iostream>
using namespace std;
ifstream in("atac.in");
ofstream out("atac.out");
const int NMAX = 32005;
const int LGMAX = 17;
vector<pair<int,int> > v[NMAX];
int n,m,x,y,a,b,c,d,p,nr,H[2*NMAX],RMQ[LGMAX][2*NMAX],K,F[NMAX],viz[NMAX],D[NMAX],lg[2*NMAX],max_depht;
struct st{
int m_min;
int nd;
};
st M[LGMAX][NMAX];
void euler(int nod,int depht){
viz[nod] = 1;
H[++K] = nod;
F[nod] = K;
D[nod] = depht;
max_depht = max(max_depht,D[nod]);
for(vector<pair<int,int> >::iterator it = v[nod].begin() ; it != v[nod].end() ; ++it)
if(!viz[(*it).first]){
euler((*it).first,depht + 1);
H[++K] = nod;
}
}
void RMQ_calc()
{
lg[1] = 0;
for(int i = 2 ; i <= K ; ++i)
lg[i] = lg[i/2] + 1;
for(int i = 1 ; i <= K ; ++i)
RMQ[0][i] = H[i];
for(int i = 1 ; i <= lg[K] ; ++i)
for(int j = 1 ; j + (1 << i) - i <= K ; ++j)
if(D[RMQ[i-1][j+(1 << (i-1))]] < D[RMQ[i-1][j]])
RMQ[i][j] = RMQ[i-1][j + (1 << (i-1))];
else
RMQ[i][j] = RMQ[i-1][j];
}
int LCA(int first,int last)
{
int unu = F[first];
int doi = F[last];
if(unu > doi)
swap(unu,doi);
int lung = doi - unu + 1;
int log = lg[lung];
int diff = lung - (1 << lg[lung]);
if(D[RMQ[log][unu]] < D[RMQ[log][unu + diff]])
return RMQ[log][unu];
return RMQ[log][unu + diff];
}
void dfs(int nod,int tata,int val)
{
viz[nod] = 1;
if(tata == -1)
M[0][nod].m_min = -1;
else{
M[0][nod].m_min = val;
M[0][nod].nd = tata;
}
for(vector<pair<int,int> >::iterator it = v[nod].begin() ; it != v[nod].end() ; ++it)
if(!viz[(*it).first])
dfs((*it).first,nod,(*it).second);
}
void calc_min_edge()
{
for(int i = 1 ; i <= lg[max_depht] ; ++i)
for(int j = 1 ; j <= n ; ++j)
if(D[j] >= (1 << i)){
M[i][j].m_min = min(M[i-1][j].m_min , M[i-1][M[i-1][j].nd].m_min);
M[i][j].nd = M[i-1][M[i-1][j].nd].nd;
}
}
int min_edge(int first,int last)
{
int diff;
int rez = 1 << 30;
do{
diff = D[last] - D[first];
if(diff != 0){
rez = min(rez,M[lg[diff]][last].m_min);
last = M[lg[diff]][last].nd;
}
}while(diff != 0);
return rez;
}
void read()
{
in>>n>>m>>p;
int m1,cost;
for(int i = 1 ; i < n ; ++i){
in>>m1>>cost;
v[m1].push_back(make_pair(i + 1,cost));
}
in>>x>>y>>a>>b>>c>>d;
in.close();
}
void solve()
{
euler(1,0);
RMQ_calc();
for(int i = 1 ; i <= n ; ++i)
viz[i] = 0;
dfs(1,-1,0);
calc_min_edge();
for(int i = 1 ; i <= m ; ++i){
int lca = LCA(x,y);
int rez = 1 << 30;
rez = min(rez,min_edge(lca,x));
rez = min(rez,min_edge(lca,y));
if(i > m - p)
out<<rez<<"\n";
x = ((x * a + y * b) %n ) + 1;
y = ((y * c + rez * d) % n) + 1;
}
out.close();
}
int main()
{
read();
solve();
return 0;
}