FPEvalDataset/LeetCodeProblem
0304
1{2 "id": 2652,3 "name": "count_number_of_possible_root_nodes",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/count-number-of-possible-root-nodes/",6 "date": "1676678400000",7 "task_description": "Alice has an undirected tree with `n` nodes labeled from `0` to `n - 1`. The tree is represented as a 2D integer array `edges` of length `n - 1` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the tree. Alice wants Bob to find the root of the tree. She allows Bob to make several **guesses** about her tree. In one guess, he does the following: Chooses two **distinct** integers `u` and `v` such that there exists an edge `[u, v]` in the tree. He tells Alice that `u` is the **parent** of `v` in the tree. Bob's guesses are represented by a 2D integer array `guesses` where `guesses[j] = [uj, vj]` indicates Bob guessed `uj` to be the parent of `vj`. Alice being lazy, does not reply to each of Bob's guesses, but just says that **at least** `k` of his guesses are `true`. Given the 2D integer arrays `edges`, `guesses` and the integer `k`, return _the **number of possible nodes** that can be the root of Alice's tree_. If there is no such tree, return `0`. **Example 1:** ``` **Input:** edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3 **Output:** 3 **Explanation:** Root = 0, correct guesses = [1,3], [0,1], [2,4] Root = 1, correct guesses = [1,3], [1,0], [2,4] Root = 2, correct guesses = [1,3], [1,0], [2,4] Root = 3, correct guesses = [1,0], [2,4] Root = 4, correct guesses = [1,3], [1,0] Considering 0, 1, or 2 as root node leads to 3 correct guesses. ``` **Example 2:** ``` **Input:** edges = [[0,1],[1,2],[2,3],[3,4]], guesses = [[1,0],[3,4],[2,1],[3,2]], k = 1 **Output:** 5 **Explanation:** Root = 0, correct guesses = [3,4] Root = 1, correct guesses = [1,0], [3,4] Root = 2, correct guesses = [1,0], [2,1], [3,4] Root = 3, correct guesses = [1,0], [2,1], [3,2], [3,4] Root = 4, correct guesses = [1,0], [2,1], [3,2] Considering any node as root will give at least 1 correct guess. ``` **Constraints:** `edges.length == n - 1` `2 <= n <= 105` `1 <= guesses.length <= 105` `0 <= ai, bi, uj, vj <= n - 1` `ai != bi` `uj != vj` `edges` represents a valid tree. `guesses[j]` is an edge of the tree. `guesses` is unique. `0 <= k <= guesses.length`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3",12 "output": "3 "13 },14 {15 "label": "Example 2",16 "input": "edges = [[0,1],[1,2],[2,3],[3,4]], guesses = [[1,0],[3,4],[2,1],[3,2]], k = 1",17 "output": "5 "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 [24 [25 0,26 127 ],28 [29 1,30 231 ],32 [33 2,34 335 ],36 [37 3,38 439 ],40 [41 3,42 543 ],44 [45 3,46 647 ],48 [49 2,50 751 ]52 ],53 [54 [55 1,56 257 ],58 [59 3,60 461 ],62 [63 2,64 365 ],66 [67 3,68 569 ]70 ],71 072 ],73 "output": 874 },75 {76 "input": [77 [78 [79 0,80 181 ]82 ],83 [84 [85 0,86 187 ]88 ],89 190 ],91 "output": 192 },93 {94 "input": [95 [96 [97 0,98 199 ],100 [101 1,102 2103 ],104 [105 1,106 3107 ]108 ],109 [110 [111 0,112 1113 ],114 [115 1,116 2117 ],118 [119 1,120 3121 ]122 ],123 3124 ],125 "output": 1126 },127 {128 "input": [129 [130 [131 0,132 1133 ],134 [135 1,136 2137 ],138 [139 1,140 3141 ],142 [143 2,144 4145 ],146 [147 4,148 5149 ]150 ],151 [152 [153 2,154 4155 ],156 [157 4,158 5159 ],160 [161 1,162 3163 ],164 [165 1,166 2167 ],168 [169 0,170 1171 ]172 ],173 0174 ],175 "output": 6176 },177 {178 "input": [179 [180 [181 0,182 1183 ],184 [185 1,186 2187 ],188 [189 1,190 3191 ],192 [193 1,194 4195 ],196 [197 4,198 5199 ],200 [201 5,202 6203 ],204 [205 1,206 7207 ],208 [209 1,210 8211 ],212 [213 6,214 9215 ]216 ],217 [218 [219 4,220 5221 ],222 [223 1,224 8225 ],226 [227 6,228 9229 ]230 ],231 3232 ],233 "output": 6234 },235 {236 "input": [237 [238 [239 0,240 1241 ],242 [243 1,244 2245 ],246 [247 0,248 3249 ],250 [251 1,252 4253 ],254 [255 4,256 5257 ],258 [259 0,260 6261 ]262 ],263 [264 [265 1,266 4267 ]268 ],269 1270 ],271 "output": 5272 },273 {274 "input": [275 [276 [277 0,278 1279 ]280 ],281 [282 [283 0,284 1285 ]286 ],287 0288 ],289 "output": 2290 },291 {292 "input": [293 [294 [295 0,296 1297 ],298 [299 1,300 2301 ],302 [303 2,304 3305 ],306 [307 0,308 4309 ],310 [311 2,312 5313 ]314 ],315 [316 [317 0,318 1319 ]320 ],321 1322 ],323 "output": 2324 },325 {326 "input": [327 [328 [329 0,330 1331 ],332 [333 1,334 2335 ]336 ],337 [338 [339 0,340 1341 ]342 ],343 1344 ],345 "output": 1346 },347 {348 "input": [349 [350 [351 0,352 1353 ],354 [355 1,356 2357 ]358 ],359 [360 [361 0,362 1363 ]364 ],365 1366 ],367 "output": 1368 }369 ],370 "haskell_template": "rootCount :: [[Int]] -> [[Int]] -> Int -> Int\nrootCount edges guesses k ",371 "ocaml_template": "let rootCount (edges: int list list) (guesses: int list list) (k: int) : int = ",372 "scala_template": "def rootCount(edges: List[List[Int]],guesses: List[List[Int]],k: Int): Int = { \n \n}",373 "java_template": "public static int rootCount(List<List<Integer>> edges, List<List<Integer>> guesses, int k) {\n\n}",374 "python_template": "class Solution(object):\n def rootCount(self, edges, guesses, k):\n \"\"\"\n :type edges: List[List[int]]\n :type guesses: List[List[int]]\n :type k: int\n :rtype: int\n \"\"\"\n "375}