Pagini recente » Cod sursa (job #2683776) | Cod sursa (job #145325) | Cod sursa (job #1019928) | Cod sursa (job #1757056) | Cod sursa (job #2697956)
#include <fstream>
#include <vector>
#include <climits>
using namespace std;
struct Edges
{
int dest, cost;
};
ifstream fin("atac.in");
ofstream fout("atac.out");
vector <Edges> v[32005];
int sz[32005], label[32005], k, level[32005], N;
int head[32005], dads[32005];
void get_size(int node, int dad)
{
sz[node]++;
dads[node] = dad;
level[node] = level[dad] + 1;
for(int i = 0; i < v[node].size(); i++)
if(v[node][i].dest != dad)
{
get_size(v[node][i].dest, node);
sz[node] += sz[v[node][i].dest];
}
}
void dfsGreu(int node, int dad)
{
label[node] = ++k;
int maxi, heavySon = v[node][0].dest;
if(heavySon == dad && v[node].size() > 1)
heavySon = v[node][1].dest;
maxi = sz[heavySon];
if(v[node].size() == 1 && dad != 0)
return;
for(int i = 0; i < v[node].size(); i++)
if(v[node][i].dest != dad && sz[v[node][i].dest] > maxi)
maxi = sz[v[node][i].dest], heavySon = v[node][i].dest;
head[heavySon] = head[node];
dfsGreu(heavySon, node);
for(int i = 0; i < v[node].size(); i++)
if(v[node][i].dest != dad && v[node][i].dest != heavySon)
dfsGreu(v[node][i].dest, node);
}
int val[32005];
struct RMQ
{
int V[20][35000];
int puteri[35000];
void build()
{
puteri[1] = 0;
for(int i = 2; i <= N; i++)
puteri[i] = puteri[i / 2] + 1;
for(int i = 1; i <= N; i++)
V[0][i] = val[i];
for(int i = 1; (1 << i) <= N; i++)
for(int j = 1; j <= N - (1 << i) + 1; j++)
V[i][j] = min(V[i - 1][j], V[i - 1][j + (1 << (i - 1))]);
}
int query(int a, int b)
{
int dif = b - a + 1;
int line = puteri[dif], column = dif - (1 << line);
return min(V[line][a], V[line][a + column]);
}
}rmq;
void get_val(int node, int cost)
{
val[label[node]] = cost;
for(int i = 0; i < v[node].size(); i++)
if(v[node][i].dest != dads[node])
get_val(v[node][i].dest, v[node][i].cost);
}
int sol(int x, int y)
{
if(head[x] == head[y])
{
int a, b;
a = label[x];
b = label[y];
if(a > b)
swap(a, b);
return rmq.query(a + 1, b);
}
if(level[head[x]] > level[head[y]])
{
int a, b;
a = label[head[x]];
b = label[x];
return min(rmq.query(a, b), sol(dads[head[x]], y));
}
else
{
int a, b;
a = label[head[y]];
b = label[y];
return min(rmq.query(a, b), sol(x, dads[head[y]]));
}
}
int main()
{
int M, P;
fin >> N >> M >> P;
for(int i = 2; i <= N; i++)
{
int x, y;
fin >> x >> y;
v[x].push_back({i, y});
v[i].push_back({x, y});
}
get_size(1, 0);
for(int i = 1; i <= N; i++)
head[i] = i;
dfsGreu(1, 0);
get_val(1, 0);
rmq.build();
int A, B, C, D, X, Y;
fin >> X >> Y >> A >> B >> C >> D;
while(M != 0)
{
int ans;
if(X == Y)
ans = 0;
else
ans = sol(X, Y);
if(M <= P)
fout << ans << '\n';
X = (X * A + Y * B) % N + 1;
Y = (Y * C + ans * D) % N + 1;
M--;
}
return 0;
}