{"code":"szorder","name":"Thứ tự cây con","description":"## Nội dung đề bài:\r\nCho một cây $n$ đỉnh, không có trọng số. Định nghĩa $S(u,r)$ là số lượng đỉnh trong cây con gốc $u$ khi gốc cây là $r$. Cho $q$ truy vấn: mỗi truy vấn đưa ra hai số nguyên dương $u,k$ $(1\\leq u,k \\leq n)$, yêu cầu tìm giá trị lớn thứ $k$ của $S(v,u)$ với $(1\\leq v\\leq n)$.\r\n## Input\r\n- Dòng $1$ chứa hai số nguyên dương $n,q$. $(1\\leq n,q \\leq 10^5)$\r\n- $n-1$ dòng tiếp theo mỗi dòng chứa $2$ số nguyên dương $u_i,v_i$ $(1\\leq u_i,v_i\\leq n,u_i\\neq v_i)$ thể hiện cạnh thứ $i$ nối trực tiếp giữa hai đỉnh $u_i,v_i$ trên cây\r\n- $q$ dòng tiếp theo, mỗi dòng có hai số nguyên dương $u,k$ $(1\\leq u,k\\leq n)$ cho mỗi truy vấn.\r\n## Output\r\n- Gồm $q$ dòng, dòng thứ $i$ chứa một số nguyên dương duy nhất là đáp án cho truy vấn thứ $i$.\r\n## Scoring\r\n- Subtask $1$ ($10\\%$ số điểm): $n,q\\leq 10^3$.\r\n- Subtask $2$ ($10\\%$ số điểm): $u_i=i,v_i=i+1$ với $1\\leq i\\leq n-1$.\r\n- Subtask $3$ ($80\\%$ số điểm): Không có ràng buộc gì thêm.\r\n## Example\r\n**Sample input**\r\n```\r\n8 4\r\n1 2\r\n2 3\r\n2 4\r\n4 5\r\n5 6\r\n5 7\r\n5 8\r\n1 4\r\n5 3\r\n4 8\r\n7 1\r\n```\r\n**Sample output**\r\n```\r\n4\r\n3\r\n1\r\n8\r\n```\r\n## Note\r\nVí dụ trong truy vấn $1$, các giá trị $S(v,1)$ sau khi được sắp xếp từ lớn đến bé là: $8,7,5,4,1,1,1,1$, giá trị lớn thứ $4$ là $4$ tương ứng với cây con gốc $5$. Các truy vấn khác cũng tương tự, có thể xem hình ảnh cho mỗi truy vấn để hiểu rõ hơn.\r\n## Hình ảnh minh họa:\r\n**Truy vấn 1:** \r\n![Imgur](https://imgur.com/fsRxhTr.png)\r\n**Truy vấn 2:**\r\n![Imgur](https://imgur.com/DLrKkfE.png)\r\n**Truy vấn 3:** \r\n![Imgur](https://imgur.com/7IoveEa.png)\r\n**Truy vấn 4:** \r\n![Imgur](https://imgur.com/ofga70h.png)","points":2000.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}