{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"Nhiệm vụ của bạn trong bài toán này là tìm LCA của hai nút $v$ và $w$ bất kỳ trong một cây $T$ cho trước.\n \u003ch3 style\u003d\"text-align: center;\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/7afea78784a923fb816b4d48a8b1dcab?v\u003d1660700659\" alt\u003d\"\"\u003e\u003c/h3\u003e\n \u003cp\u003e\u003cstrong\u003eVí dụ LCA của các nút 9 và 12 trong cây này là nút số 3.\u003c/strong\u003e\u003c/p\u003e\n### Dữ liệu\n- Dòng 1: ghi số lượng truy vấn cần thực hiện. \n- Tiếp theo là các truy vấn, mỗi truy vấn gồm:\n - Dòng thứ nhất ghi số nguyên $N$ $(1 ≤ N≤ 1000)$ là số nút của cây. Các nút được đánh số từ $1$ đến $N$. \n - $N$ dòng tiếp theo, dòng thứ $i$ $(\\forall i \u003d 1 \\to N)$ bắt đầu với số nguyên $M$ (0 ≤ M ≤ 999) là số lượng nút con của nút thứ $i$, sau đó là $M$ số ứng với các nút con của nút $i$. \n - Dòng tiếp theo ghi số $Q$ số lượng cặp đỉnh cần tìm LCA , $1 ≤ Q ≤ 1000$. \n - $Q$ dòng tiếp theo, mỗi dòng ghi hai số $v, w$ $ (1≤ v, w ≤ 1,000)$ yêu cầu tìm LCA của $v$ và $w$ trong cây $T$.\n- Dữ liệu vào đảm bảo cây chỉ có một gốc và không có chu trình.\n\n### Kết quả\n- Đối với mỗi truy vấn, in ra trên $ Q + 1 $ dòng gồm:\n - Dòng đầu tiên ghi `Case C:` trong đó $C$ là số thứ tự của truy vấn, bắt đầu từ $1$.\n - $Q$ dòng tiếp theo ghi LCA của cặp $v$ và $w$ tương ứng.\n\n### Ví dụ\n\n\u003c/div\u003e\n\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\u003e1\n7\n3 2 3 4\n0\n3 5 6 7\n0\n0\n0\n0\n2\n5 7\n2 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1:\n3\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}