Pagini recente » Cod sursa (job #647158) | Cod sursa (job #742043) | Cod sursa (job #1004707) | Cod sursa (job #2456921) | Cod sursa (job #1946878)
#include <forward_list>
#include <fstream>
#include <vector>
using namespace std;
struct Node
{
int position;
int level;
forward_list<int> edges;
};
using Tree = vector<Node>;
template <class T>
using Matrix = vector<vector<int>>;
void Euler(Tree &t, int node, vector<int> &res)
{
res.push_back(node);
t[node].position = res.size() - 1;
for (int next : t[node].edges) {
t[next].level = t[node].level + 1;
Euler(t, next, res);
res.push_back(node);
}
}
vector<int> Dfs(Tree &t, int root)
{
t[root].level = 0;
vector<int> euler;
Euler(t, root, euler);
return euler;
}
Matrix<int> RmqPrecalc(Tree &t, int root)
{
auto euler = Dfs(t, root);
Matrix<int> rmq(euler.size(), vector<int>(20, -1));
for (unsigned i = 0; i < euler.size(); ++i) {
rmq[i][0] = euler[i];
}
for (int p = 1; p < 20; ++p) {
for (int i = euler.size() - 1; i - (1 << p) + 1 >= 0; --i) {
int a = rmq[i][p - 1];
int left = i - (1 << p) + 1;
int b = rmq[left + (1 << (p - 1)) - 1][p - 1];
rmq[i][p] = (t[a].level < t[b].level) ? a : b;
}
}
return rmq;
}
int FindLca(const Tree &t, const Matrix<int> &rmq, int x, int y)
{
x = t[x].position;
y = t[y].position;
if (x > y) {
swap(x, y);
}
int len = y - x + 1;
int pow = 0;
while ((1 << pow) <= len) {
++pow;
}
--pow;
int a = rmq[y][pow];
int b = rmq[x + (1 << pow) - 1][pow];
return (t[a].level < t[b].level) ? a : b;
}
int main()
{
ifstream fin("lca.in");
ofstream fout("lca.out");
int n, q;
fin >> n >> q;
Tree tree(n);
for (int i = 1; i < n; ++i) {
int fa;
fin >> fa;
tree[fa - 1].edges.push_front(i);
}
auto rmq = RmqPrecalc(tree, 0);
while (q--) {
int x, y;
fin >> x >> y;
fout << FindLca(tree, rmq, x - 1, y - 1) + 1 << "\n";
}
return 0;
}