{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Một cây gốc là một cấu trúc dữ liệu nổi tiếng trong khoa học máy tính và kỹ thuật. Một ví dụ được hiển thị dưới đây: \n\u003cbr\u003e \n\u003cbr\u003e\u003cimg src\u003d\"CDN_BASE_URL/a4cf40017a91cfbd4f81b13b267ec9ee?v\u003d1710196159\"\u003e \n\u003cbr\u003eTrong hình vẽ, mỗi nút được gán nhãn bằng một số nguyên từ {1, 2,...,16}. Nút 8 là gốc của cây. Nút x là tổ tiên của nút y nếu nút x nằm trên đường đi giữa gốc và nút y. Ví dụ, nút 4 là tổ tiên của nút 16. Nút 10 cũng là tổ tiên của nút 16. Trên thực tế, các nút 8, 4, 10 và 16 là tổ tiên của nút 16. Hãy nhớ rằng một nút là tổ tiên của chính nó. Các nút 8, 4, 6 và 7 là tổ tiên của nút 7. Một nút x được gọi là tổ tiên chung của hai nút khác nhau y và z nếu nút x là tổ tiên của nút y và là tổ tiên của nút z. Do đó, các nút 8 và 4 là tổ tiên chung của các nút 16 và 7. Một nút x được gọi là tổ tiên chung gần nhất của hai nút y và z nếu x là tổ tiên chung của y và z và gần nhất với y và z trong số các tổ tiên chung của họ. Do đó, tổ tiên chung gần nhất của các nút 16 và 7 là nút 4. Nút 4 gần hơn với các nút 16 và 7 hơn nút 8. \n\u003cbr\u003e \n\u003cbr\u003eĐối với các ví dụ khác, tổ tiên chung gần nhất của các nút 2 và 3 là nút 10, tổ tiên chung gần nhất của các nút 6 và 13 là nút 8, và tổ tiên chung gần nhất của các nút 4 và 12 là nút 4. Trong ví dụ cuối cùng, nếu y là tổ tiên của z, thì tổ tiên chung gần nhất của y và z là y. \n\u003cbr\u003e \n\u003cbr\u003eViết một chương trình để tìm tổ tiên chung gần nhất của hai nút khác nhau trong một cây. \n\u003cbr\u003e \n\u003cbr\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"Đầu vào bao gồm T bài kiểm tra. Số lượng bài kiểm tra (T) được cho trong dòng đầu tiên của tệp đầu vào. Mỗi bài kiểm tra bắt đầu bằng một dòng chứa một số nguyên N, số nút trong một cây, 2\u003c\u003dN\u003c\u003d10,000. Các nút được gán nhãn bằng các số nguyên 1, 2,..., N. Mỗi trong N -1 dòng tiếp theo chứa một cặp số nguyên đại diện cho một cạnh --số nguyên đầu tiên là nút cha của số nguyên thứ hai. Lưu ý rằng một cây với N nút có chính xác N - 1 cạnh. Dòng cuối cùng của mỗi bài kiểm tra chứa hai số nguyên khác nhau mà tổ tiên chung gần nhất cần được tính toán."}},{"title":"Đầu ra","value":{"format":"HTML","content":"In chính xác một dòng cho mỗi bài kiểm tra. Dòng này nên chứa số nguyên là tổ tiên chung gần nhất."}},{"title":"Ví dụ","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n16\r\n1 14\r\n8 5\r\n10 16\r\n5 9\r\n4 6\r\n8 4\r\n4 10\r\n1 13\r\n6 15\r\n10 11\r\n6 7\r\n10 2\r\n16 3\r\n8 1\r\n16 12\r\n16 7\r\n5\r\n2 3\r\n3 4\r\n3 1\r\n1 5\r\n3 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n3\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}