{"problem":{"name":"B. Crush","description":{"content":"B là một anh chàng chuyên tin đz, ngầu lòi. Anh chàng coder của chúng ta hiện đang crush một cô nàng chuyên Nga xinh xắn, hiền lành, C. Nhưng do khoảng cách địa lý giữa hai tòa nhà A1 và A2 nên B khôn","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10227B"},"statements":[{"statement_type":"Markdown","content":"B là một anh chàng chuyên tin đz, ngầu lòi. Anh chàng coder của chúng ta hiện đang crush một cô nàng chuyên Nga xinh xắn, hiền lành, C. Nhưng do khoảng cách địa lý giữa hai tòa nhà A1 và A2 nên B không thể nhìn thấy C mỗi giờ ra chơi. \n\nNhưng dựa vào tài năng \"_Hắc cơ_\" của mình, anh đã hack được camera của trường chỉ dựa vào chiếc điện thoại của mình. Nhưng anh không ngờ rằng ông mặt nhăn bảo vệ trường thật ra chính là trùm cuối trong đường dây gian lận thi cử.\n\nÔng đã thiết kế mạng lưới camera rất tinh vi, là một mạng liên thông có N - 1 đường kết nối, không có chu trình và một số camera cần có mật khẩu mới có thể truy cập. Tất nhiên B vẫn phá được mật khẩu nhưng sẽ bị mất 1 năng lượng pin điện thoại. Bạn hãy giúp B đếm số cách sử dụng đúng K năng lượng để truy cập các camera để anh có thể triệt phá đường dây và chinh phục crush của mình nhé.\n\nDòng đầu tiên chứa 2 số nguyên N, K lần lượt là số camera và số năng lượng pin.\n\nDòng thứ hai chứa N số nguyên là 0 / 1 biểu thị camera thứ i có mật khẩu hay không.\n\nN - 1 dòng tiếp theo chứa 2 số nguyên u, v biểu thị có đường kết nối giữa camera u và camera v.\n\nIn ra một dòng duy nhất là kết quả bài toán.\n\n1 ≤ N ≤ 50000.\n\n1 ≤ K ≤ 100.\n\n20% số test với N ≤ 25.\n\n30% số test với N ≤ 1000.\n\n20% số test với K ≤ 10.\n\nGiải thích test 1: {1, 2, 3}, {2, 5}, {1, 3, 4}, {1, 2, 5}, {1, 2, 4}.\n\nGiải thích test 2: {1}, {3}, {1, 2}.\n\nGiải thích test 3: {}. (tập rỗng)\n\n## Input\n\nDòng đầu tiên chứa 2 số nguyên N, K lần lượt là số camera và số năng lượng pin.Dòng thứ hai chứa N số nguyên là 0 / 1 biểu thị camera thứ i có mật khẩu hay không.N - 1 dòng tiếp theo chứa 2 số nguyên u, v biểu thị có đường kết nối giữa camera u và camera v.\n\n## Output\n\nIn ra một dòng duy nhất là kết quả bài toán.\n\n[samples]\n\n## Scoring\n\n1 ≤ N ≤ 50000.1 ≤ K ≤ 100.20% số test với N ≤ 25.30% số test với N ≤ 1000.20% số test với K ≤ 10.\n\n## Note\n\nGiải thích test 1: {1, 2, 3}, {2, 5}, {1, 3, 4}, {1, 2, 5}, {1, 2, 4}.Giải thích test 2: {1}, {3}, {1, 2}.Giải thích test 3: {}. (tập rỗng)","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n - 1 $.  \nLet $ h \\in V $ be the hidden node (unknown).  \n\n**Query Types**  \nFor any node $ u \\in V $:  \n- Type 1: $ q_1(u) = \\text{distance}(u, h) $  \n- Type 2: $ q_2(u) = \\begin{cases} \n\\text{second node on the unique path from } u \\text{ to } h & \\text{if } u \\ne h \\\\\n0 & \\text{if } u = h \n\\end{cases} $  \n\n**Constraints**  \n1. $ 1 \\le n \\le 200000 $  \n2. At most 36 queries allowed.  \n\n**Objective**  \nIdentify $ h $ using at most 36 queries of type $ q_1 $ or $ q_2 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10227B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}