Pagini recente » Cod sursa (job #1006967) | Cod sursa (job #821391) | Cod sursa (job #132283) | Cod sursa (job #1132368) | Cod sursa (job #1964946)
#include <stdio.h>
#include <stdlib.h>
#define LOG 20
typedef struct ListNode
{
int value;
struct ListNode *next;
} ListNode;
typedef struct List
{
ListNode *left, *right;
} List;
ListNode *CreateListNode(int value)
{
ListNode *new_node = (ListNode*)malloc(sizeof(ListNode));
*new_node = (ListNode){value, NULL};
return new_node;
}
void AddToList(List *list, int value)
{
ListNode *new_node = CreateListNode(value);
if (list->left == NULL) {
list->left = list->right = new_node;
} else {
list->right->next = new_node;
list->right = new_node;
}
}
typedef struct TreeNode
{
int ancestors[LOG];
int nanc;
int exit;
List sons;
} TreeNode;
TreeNode* CreateTree(int size)
{
TreeNode *tree = (TreeNode*)malloc(size * sizeof(TreeNode));
int i;
for (i = 0; i < size; ++i) {
tree[i].nanc = tree[i].exit = 0;
tree[i].sons = (List){NULL, NULL};
}
return tree;
}
void Dfs(TreeNode *t, int node, int st[], int nst)
{
static int time = 0;
st[nst] = node;
if (nst > 0) {
int fa = st[nst - 1];
int ord = 1;
t[node].ancestors[0] = fa;
while ((1 << ord) < nst) {
t[node].ancestors[ord] = t[fa].ancestors[ord - 1];
fa = t[fa].ancestors[ord - 1];
++ord;
}
t[node].nanc = ord;
}
ListNode *it = t[node].sons.left;
while (it != NULL) {
Dfs(t, it->value, st, nst + 1);
it = it->next;
}
t[node].exit = ++time;
}
void Swap(int *a, int *b)
{
int aux = *a;
*a = *b;
*b = aux;
}
int Lca(TreeNode *t, int x, int y)
{
if (x == y) {
return x;
}
if (t[x].exit > t[y].exit) {
Swap(&x, &y);
}
int ind = 0;
while (ind < t[x].nanc) {
int fa = t[x].ancestors[ind];
if (t[fa].exit > t[y].exit) {
break;
}
++ind;
}
if (ind > 0) {
--ind;
}
return Lca(t, y, t[x].ancestors[ind]);
}
int main()
{
FILE *fin = fopen("lca.in", "r");
FILE *fout = fopen("lca.out", "w");
int n, q, i, fa, x, y;
fscanf(fin, "%d%d",&n, &q);
TreeNode *tree = CreateTree(n);
for (i = 1; i < n; ++i) {
fscanf(fin, "%d", &fa);
AddToList(&tree[fa - 1].sons, i);
}
int *stack = (int*)malloc(n * sizeof(int));
Dfs(tree, 0, stack, 0);
free(stack);
while (q--) {
fscanf(fin, "%d%d", &x, &y);
fprintf(fout, "%d\n", Lca(tree, x - 1, y - 1) + 1);
}
free(tree);
return 0;
}