Cod sursa(job #1574946)
| Utilizator | Data | 20 ianuarie 2016 22:41:36 | |
|---|---|---|---|
| Problema | Lowest Common Ancestor | Scor | 10 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.68 kb |
#include <fstream>
using namespace std;
ifstream f("lca.in");
ofstream g("lca.out");
const int Nmax = 100005;
int n, m, t[Nmax], r[Nmax];
void Read()
{
f>>n>>m;
for(int i = 2; i <= n; i++)
{
f>>t[i];
r[i] = r[t[i]] + 1;
}
}
void Solve()
{
int x, y;
while(m--)
{
f>>x>>y;
if(x < y) swap(x,y);
while(r[x] > r[y]) x = t[x];
if(x == y) g<<x<<'\n';
else
{
while(x != y)
{
x = t[x];
y = t[y];
}
g<<x<<'\n';
}
}
}
int main()
{
Read();
Solve();
return 0;
}
