---
# System prepended metadata

title: 'Câu 3 : (4.0 điểm) Nút cha chung gần nhất'

---

# Câu 3 : (4.0 điểm) Nút cha chung gần nhất

 Cây là một cấu trúc dữ liệu có nhiều ứng dụng trong tin học. Ví dụ ta cso cây với $16$ nút, các nút được đánh số từ 1 tới $16$, nút $8$ là gốc, như hình sau :
 
 Nút $x$ được gọi là nút cha của $y$ nếu tồn tại một đường dẫn từ gốc tới $y$ đi qua $x$. Ở cây đang xét, nút $4$ là nút cha của nút $16$, nút $10$ cũng là nút cha của $16$.
 
 ![](https://hackmd.io/_uploads/BJP64gV-6.png)
 
 Một nút đồng thời là nút cha của chính mình. Ở cây đang xét, các nút $8, 4, 10$ và $16$ là nút cha của $16$
 
 Nút $x$ được gọi là nút cha chung của 2 nút khác nhau $y$ và $z$ nếu nó vừa là nút cha của $y$, vừa là của $z$. Ở cây đang xét, các nút $8$ và $4$ đều là nút cha chung của các nút $7$ và $16$.
 
 Nút $x$ được gọi là nút cha chung gần nhất của $y$ và $z$ nếu nó là nút cha chugn của 2 nút này và trên đường dẫn từ $x$ tới $y$ không còn nút cha chung nào khác của $y$ và $z$. Ở cây đang xét, $4$ là nút cha chung gần nhất của $7$ và $16$.
 
 Cho một cây gồm $N$ nút, các nút được đánh số từ $1$ đến $N$.
 
 **Yêu cầu**
 
 Xác định nút cha chung gần nhất của 2 nút khác nhau trên cây 
 
 **Input**
 
 *Dòng 1* : Chứa 2 số nguyên dương $N$ và $K$. Trong đó $N$ là số lượng nút cây, $K$ là chỉ số nút gốc. $(2<=N<=10000)$
 
 *$N-1$ dòng tiếp theo :* mỗi dòng chứa 2 số nguyên dương $x$ và $y$ , là chỉ số 2 nút liên tiếp cây với $x$ là nút cha của nút $y$.
 
 *Dòng cuối cùng :* chứa 2 số nguyên khác nhau là chỉ số 2 nút cần tìm nút cha chung gần nhất.
 
 Các số trên cùng 1 dòng được ghi cách nhau ít nhất một dấu cách.
 
 **Output**
 
 *Dòng 1* : Ghi một số nguyên dương là chỉ số nút cha chung gần nhất tìm được.
 
 **Example**
 
>  **Input**
>  
>  16 8
>  1 14
>  8 5 
>  10 16
>  5 9
>  4 6
>  8 4
>  4 10
>  1 13
>  6 15
>  10 11
>  6 7
>  10 2
>  16 3
>  8 1
>  16 12
>  16 7
 
>  **Output**
>  
>  4
 
 
 


 