Pagini recente » Cod sursa (job #2640486) | Cod sursa (job #2712012) | Cod sursa (job #147862) | Cod sursa (job #308651) | Cod sursa (job #1419572)
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
using namespace std;
#define Nmax 32005
#define logNmax 20
#define inf 0x3f3f3f3f
long long N,M,P,A,B,C,D,X,Y;
vector< pair<int,int> > Adj[Nmax];
int T[logNmax][Nmax];
int dp[logNmax][Nmax];
int L[Nmax];
void dfs(int s)
{
for(auto p: Adj[s]) {
if(T[0][s] == p.first) continue;
L[p.first] = L[s] + 1;
T[0][p.first] = s;
dp[0][p.first] = p.second;
dfs(p.first);
}
}
void build_LCA()
{
for(int k = 1; (1 << k) <= N; k++)
for(int i = 1; i <= N; i++)
T[k][i] = T[k-1][T[k-1][i]];
}
void build_dp()
{
for(int k = 1; (1 << k) <= N; k++)
for(int i = 1; i <= N; i++)
dp[k][i] = min(dp[k-1][i],dp[k-1][T[k-1][i]]); // dp[k][i] = cel mai mic element de pe lantul
// dintre i si al 2^k - lea stramos
}
int lca(int x,int y)
{
if(L[x] < L[y])
swap(x,y);
int log1,log2;
for(log1 = 0; log1 < L[x]; log1++);
for(log2 = 0; log2 < L[y]; log2++);
for(int k = log1; k >= 0; k--)
if(L[x] - (1 << k) >= L[y])
x = T[k][x];
if(x == y) return x;
for(int k = log2; k >= 0; k--)
if(T[k][x] != T[k][y] && T[k][x] != 0) {
x = T[k][x];
y = T[k][y];
}
return T[0][x];
}
int k_th_Ancestor(int x,int k)
{
int log;
for(log = 0; (1 << log) < k; log++);
for(int j = log; j >= 0 && k; j--)
if(k >= (1 << j)) {
k -= (1 << j);
x = T[j][x];
}
return x;
}
int rmq(int x,int y) // on chain x,y
{
if(x == y) return inf;
if(L[x] < L[y])
swap(x,y);
int k;
for(k = 0; (1 << k) <= L[x] - L[y]; k++);
k--;
int mid = k_th_Ancestor(x,L[x] - L[y] - (1 << k));
if(dp[k][x] > dp[k][mid])
return dp[k][mid];
return dp[k][x];
}
int query(int x,int y)
{
if(x == y) return 0;
int l = lca(x,y);
return min(rmq(l,x),rmq(l,y));
}
int main()
{
ifstream fin("atac.in");
ofstream fout("atac.out");
fin >> N >> M >> P;
for(int i = 2; i <= N; i++) {
int u,v;
fin >> u >> v;
Adj[i].push_back(make_pair(u,v));
Adj[u].push_back(make_pair(i,v));
}
fin >> X >> Y >> A >> B >> C >> D;
L[1] = 1;
dfs(1);
build_LCA();
build_dp();
for(long long i = 1, Z = query(X,Y); i <= M; i++) {
if(i >= M - P + 1)
fout << Z << "\n";
X = (X*A + Y*B)%N + 1;
Y = (Y*C + Z*D)%N + 1;
Z = query(X,Y);
}
}