# 11231: 【原1231】lca

### 题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1231

P332.3

## Sample Input

``````7 4 6
2 3
4 5
6 7
0 0
0 0
0 0
0 0
``````

## Sample Output

``````1
``````

## 样例解释

``````            1
/ \
/   \
2     3
/ \   / \
4!  5 6!  7
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "queue"
#include "cmath"
#include "stack"
#include "cstring"
using namespace std;

//二叉树类
template <class T>
class myBinaryTree {
public:
class node {
public:
T data;
node* lchild = nullptr, * rchild = nullptr, * parent = nullptr;
};
node* root = nullptr;
node** nodeList = nullptr;
long long sizeOfTree = 0;

//创建一个相应大小的树
void createTree(int num) {
nodeList = new node * [num + 1]{ nullptr };
sizeOfTree = num;
}
//创建结点（全部完成后需要CheckRoot进行根节点识别）
void createNode(int nodeNum, int lchild, int rchild, T data) {
if (nodeList[nodeNum] == nullptr)
nodeList[nodeNum] = new node;

nodeList[nodeNum]->data = data;

if (lchild != 0) {
if (nodeList[lchild] == nullptr)
nodeList[lchild] = new node;
nodeList[lchild]->parent = nodeList[nodeNum];
nodeList[nodeNum]->lchild = nodeList[lchild];
}

if (rchild != 0) {
if (nodeList[rchild] == nullptr)
nodeList[rchild] = new node;
nodeList[rchild]->parent = nodeList[nodeNum];
nodeList[nodeNum]->rchild = nodeList[rchild];
}
}
//创建一个num大小的树，数据为treeData
void createTree(T * treeData, int num) {
createTree(num);
for (int i = 1; i <= num; i++) {
int lchild = i * 2 <= num ? i * 2 : 0,
rchild = i * 2 + 1 <= num ? i * 2 + 1 : 0;
createNode(i, lchild, rchild, treeData[i - 1]);
}
checkRoot();
}

void checkRoot() {
for (int i = 1; i <= sizeOfTree; i++) {
if (nodeList[i]->parent == nullptr) {
root = nodeList[i];
break;
}
}
}

//清空
void clear() {
clear(root);
}

void clear(node * p) {
if (p == nullptr)
return;
clear(p->lchild);
clear(p->rchild);
delete p;
p = nullptr;
}

//构造
myBinaryTree() {}

//析构
~myBinaryTree() {
clear(root);
}

//判断是否非空
bool empty() {
return root == nullptr;
}

//返回大小
long long size() {
return sizeOfTree;
}
};

int ans = 0;
//lca(节点)
int lca(myBinaryTree<int>::node* curNode, int d1, int d2) {
if (curNode == nullptr)
return 0;
auto l = lca(curNode->lchild, d1, d2), r = lca(curNode->rchild, d1, d2);
if (ans > 0)
return 2;
else if (l + r + int(curNode->data == d1 || curNode->data == d2) >= 2) {
ans = curNode->data;
return 2;
}
else
return l + r + int(curNode->data == d1 || curNode->data == d2);
}

int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);

myBinaryTree<int> bTree;
int N, X, Y;
cin >> N >> X >> Y;

bTree.createTree(N);
for (int i = 1; i <= N; i++) {
int lchild, rchild;
cin >> lchild >> rchild;
bTree.createNode(i, lchild, rchild, i);
}
bTree.checkRoot();
lca(bTree.root, X, Y);
cout << ans;

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 1e6 + 100;

int size1 = 0;
long long N, X, Y, Xtemp, Ytemp;
long long father[maxN] = {0}, XFather[maxN] = {0};

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin >> N >> X >> Y;
long long temp1, temp2;

for (long long i = 1; i <= N; i++) {
cin >> temp1 >> temp2;
if (temp1 != 0) {
father[temp1] = i;
}
if (temp2 != 0) {
father[temp2] = i;
}
}

Xtemp = X;
Ytemp = Y;
while (Xtemp != 0) {
XFather[size1++] = Xtemp;
Xtemp = father[Xtemp];
}

while (Ytemp != 0) {
for (int i = 0; i < size1; i++) {
if (XFather[i] == Ytemp) {
cout << Ytemp << '\n';
return 0;
}
}

Ytemp = father[Ytemp];
}

return 0;
}
``````

## yyong119's solution

``````#include <iostream>
using namespace std;

int N, X, Y;

struct node {
int left, right, parent;
node() :left(0), right(0), parent(0) {}
};

node *tree;

class disjointSet {
private:
int *parent;

public:
disjointSet(int n) {
parent = new int[n + 1];
for (int i = 0; i < n; ++i)parent[i + 1] = -1;
parent[0] = 0;
}
~disjointSet() {
delete[]parent;
}
int find(int x) {
if (parent[x]<0)return x;
return parent[x] = find(parent[x]);
}
void merge(int root1, int root2) {
if (tree[root1].parent == root2) {
parent[root2] += parent[root1];
parent[root1] = root2;
}
else {
parent[root1] += parent[root2];
parent[root2] = root1;
}
}
};

int LCA(disjointSet& d, node *t, int root) {
if (!root)return -1;
int tmp;
if ((tmp = LCA(d, t, t[root].left)) > 0)return tmp;
else if ((tmp = LCA(d, t, t[root].right) > 0))return tmp;
else {
if (t[root].left)d.merge(root, t[root].left);
if (t[root].right)d.merge(root, t[root].right);
if ((tmp = d.find(X)) == d.find(Y))return tmp;
else return -1;
}
}

int main() {
ios::sync_with_stdio(false);
cin >> N >> X >> Y;
tree = new node[N + 1];
for (int i = 1; i <= N; ++i) {
cin >> tree[i].left >> tree[i].right;
tree[tree[i].left].parent = tree[tree[i].right].parent = i;
}
int root = 1;
while (tree[root].parent)root = tree[root].parent;
disjointSet d(N);
cout << LCA(d, tree, root) << endl;
delete[]tree;
return 0;
}
``````