Pagini recente » Cod sursa (job #2645643) | Cod sursa (job #1409219) | Cod sursa (job #1968714) | Cod sursa (job #609311) | Cod sursa (job #2852747)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int NMAX = 32000 + 5;
const int LOG = 16;
int N, M, P;
int x, y, a, b, c, d;
struct elem
{
int nod, cost;
};
vector<elem> g[NMAX];
int depth[NMAX];
int up[NMAX][LOG];
int rmqMin[NMAX][LOG];
vector<int> answers;
void dfs(int fiu, int tata)
{
depth[fiu] = 1 + depth[tata];
for(int i = 1; i < LOG; i ++)
{
up[fiu][i] = up[up[fiu][i - 1]][i - 1];
}
for(int i = 1; i < LOG; i ++)
{
rmqMin[fiu][i] = min(rmqMin[fiu][i - 1], rmqMin[up[fiu][i - 1]][i - 1]);
}
for(auto it : g[fiu])
{
if(it.nod != tata)
{
up[it.nod][0] = fiu;
rmqMin[it.nod][0] = it.cost;
dfs(it.nod, fiu);
}
}
}
int query(int x, int y)
{
if(depth[x] < depth[y])
{
swap(x, y);
}
int dif = depth[x] - depth[y];
int ans = (1 << 30);
for(int i = LOG - 1; i >= 0; i --)
{
if(dif & (1 << i))
{
ans = min(ans, rmqMin[x][i]);
x = up[x][i];
}
}
if(x == y)
{
return ans;
}
for(int i = LOG - 1; i >= 0; i --)
{
if(up[x][i] != up[y][i])
{
ans = min(ans, rmqMin[x][i]);
ans = min(ans, rmqMin[y][i]);
x = up[x][i];
y = up[y][i];
}
}
ans = min(ans, min(rmqMin[x][0], rmqMin[y][0]));
return ans;
}
int main()
{
fin >> N >> M >> P;
for(int i = 2; i <= N; i ++)
{
int u, v;
fin >> u >> v;
g[u].push_back({i, v});
g[i].push_back({u, v});
}
dfs(1, 0);
fin >> x >> y >> a >> b >> c >> d;
for(int i = 2; i <= M; i ++)
{
int z;
if(x == y)
{
z = 0;
}
else
{
z = query(x, y);
}
answers.push_back(z);
x = (x * a + y * b) % N + 1;
y = (y * c + z * d) % N + 1;
}
for(int i = answers.size() - P; i < answers.size(); i ++)
{
fout << answers[i] << '\n';
}
return 0;
}