FPEvalDataset/LeetCodeProblem
0304
1{2 "id": 3307,3 "name": "find_the_maximum_sum_of_node_values",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/find-the-maximum-sum-of-node-values/",6 "date": "2024-02-17 00:00:00",7 "task_description": "There exists an **undirected** tree with `n` nodes numbered `0` to `n - 1`. You are given a **0-indexed** 2D integer array `edges` of length `n - 1`, where `edges[i] = [ui, vi]` indicates that there is an edge between nodes `ui` and `vi` in the tree. You are also given a **positive** integer `k`, and a **0-indexed** array of **non-negative** integers `nums` of length `n`, where `nums[i]` represents the **value** of the node numbered `i`. Alice wants the sum of values of tree nodes to be **maximum**, for which Alice can perform the following operation **any** number of times (**including zero**) on the tree: Choose any edge `[u, v]` connecting the nodes `u` and `v`, and update their values as follows: `nums[u] = nums[u] XOR k` `nums[v] = nums[v] XOR k` Return _the **maximum** possible **sum** of the **values** Alice can achieve by performing the operation **any** number of times_. **Example 1:** ``` **Input:** nums = [1,2,1], k = 3, edges = [[0,1],[0,2]] **Output:** 6 **Explanation:** Alice can achieve the maximum sum of 6 using a single operation: - Choose the edge [0,2]. nums[0] and nums[2] become: 1 XOR 3 = 2, and the array nums becomes: [1,2,1] -> [2,2,2]. The total sum of values is 2 + 2 + 2 = 6. It can be shown that 6 is the maximum achievable sum of values. ``` **Example 2:** ``` **Input:** nums = [2,3], k = 7, edges = [[0,1]] **Output:** 9 **Explanation:** Alice can achieve the maximum sum of 9 using a single operation: - Choose the edge [0,1]. nums[0] becomes: 2 XOR 7 = 5 and nums[1] become: 3 XOR 7 = 4, and the array nums becomes: [2,3] -> [5,4]. The total sum of values is 5 + 4 = 9. It can be shown that 9 is the maximum achievable sum of values. ``` **Example 3:** ``` **Input:** nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]] **Output:** 42 **Explanation:** The maximum achievable sum is 42 which can be achieved by Alice performing no operations. ``` **Constraints:** `2 <= n == nums.length <= 2 * 104` `1 <= k <= 109` `0 <= nums[i] <= 109` `edges.length == n - 1` `edges[i].length == 2` `0 <= edges[i][0], edges[i][1] <= n - 1` The input is generated such that `edges` represent a valid tree.",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]",12 "output": "6 "13 },14 {15 "label": "Example 2",16 "input": "nums = [2,3], k = 7, edges = [[0,1]]",17 "output": "9 "18 },19 {20 "label": "Example 3",21 "input": "nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]",22 "output": "42 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 [29 977538041,30 914985843,31 221838576,32 501483518,33 488047899,34 707773864,35 824502743,36 115109856,37 140156554,38 10586824,39 50988438,40 577753314,41 285640935,42 817005225,43 299414865,44 884300312,45 659005571,46 68365812347 ],48 220908190,49 [50 [51 0,52 153 ],54 [55 1,56 257 ],58 [59 2,60 361 ],62 [63 1,64 465 ],66 [67 4,68 569 ],70 [71 5,72 673 ],74 [75 3,76 777 ],78 [79 1,80 881 ],82 [83 8,84 985 ],86 [87 1,88 1089 ],90 [91 10,92 1193 ],94 [95 7,96 1297 ],98 [99 8,100 13101 ],102 [103 7,104 14105 ],106 [107 11,108 15109 ],110 [111 11,112 16113 ],114 [115 10,116 17117 ]118 ]119 ],120 "output": 10809396445121 },122 {123 "input": [124 [125 949981876,126 11477663,127 618727282,128 869248515,129 954828286,130 963523325,131 746318200,132 14800663,133 364276796,134 12281068,135 398856652,136 421492724,137 555042350,138 87423989,139 10573301,140 636578468,141 292942321,142 225186788143 ],144 763265655,145 [146 [147 0,148 1149 ],150 [151 0,152 2153 ],154 [155 2,156 3157 ],158 [159 2,160 4161 ],162 [163 2,164 5165 ],166 [167 2,168 6169 ],170 [171 2,172 7173 ],174 [175 3,176 8177 ],178 [179 4,180 9181 ],182 [183 2,184 10185 ],186 [187 5,188 11189 ],190 [191 9,192 12193 ],194 [195 9,196 13197 ],198 [199 5,200 14201 ],202 [203 2,204 15205 ],206 [207 1,208 16209 ],210 [211 14,212 17213 ]214 ]215 ],216 "output": 14404175351217 },218 {219 "input": [220 [221 745311166,222 850593829,223 117376415,224 112862397,225 220549307,226 911445538,227 834876316,228 849475440,229 81818436,230 406272938,231 128674880,232 833156998,233 214081401,234 606693707,235 796952554,236 274223460,237 426632282,238 314538858,239 518198322,240 575086589241 ],242 968161642,243 [244 [245 0,246 1247 ],248 [249 0,250 2251 ],252 [253 2,254 3255 ],256 [257 2,258 4259 ],260 [261 2,262 5263 ],264 [265 4,266 6267 ],268 [269 4,270 7271 ],272 [273 5,274 8275 ],276 [277 1,278 9279 ],280 [281 8,282 10283 ],284 [285 2,286 11287 ],288 [289 6,290 12291 ],292 [293 10,294 13295 ],296 [297 7,298 14299 ],300 [301 4,302 15303 ],304 [305 6,306 16307 ],308 [309 7,310 17311 ],312 [313 0,314 18315 ],316 [317 0,318 19319 ]320 ]321 ],322 "output": 16066485697323 },324 {325 "input": [326 [327 44291611,328 386215946,329 375861387,330 504839330,331 84457102,332 951788380,333 827948560,334 246022760335 ],336 310790086,337 [338 [339 0,340 1341 ],342 [343 1,344 2345 ],346 [347 1,348 3349 ],350 [351 3,352 4353 ],354 [355 0,356 5357 ],358 [359 4,360 6361 ],362 [363 4,364 7365 ]366 ]367 ],368 "output": 3959341884369 },370 {371 "input": [372 [373 391658618,374 10284122,375 964167617,376 293237510,377 906154707,378 888486155,379 390244058,380 246905744,381 453161757,382 289165279,383 993194070,384 458759549,385 870761519386 ],387 91858911,388 [389 [390 0,391 1392 ],393 [394 0,395 2396 ],397 [398 1,399 3400 ],401 [402 0,403 4404 ],405 [406 0,407 5408 ],409 [410 0,411 6412 ],413 [414 0,415 7416 ],417 [418 6,419 8420 ],421 [422 5,423 9424 ],425 [426 9,427 10428 ],429 [430 6,431 11432 ],433 [434 3,435 12436 ]437 ]438 ],439 "output": 7583473179440 },441 {442 "input": [443 [444 53742462,445 631248016,446 157640466,447 540450446,448 197211472,449 908831573,450 636352024,451 681393970,452 968786857,453 802549093,454 344688510,455 537896129,456 227515237,457 662975492,458 951612635,459 253708898,460 187242418,461 354643418,462 814465367463 ],464 388231932,465 [466 [467 0,468 1469 ],470 [471 1,472 2473 ],474 [475 0,476 3477 ],478 [479 2,480 4481 ],482 [483 1,484 5485 ],486 [487 4,488 6489 ],490 [491 3,492 7493 ],494 [495 2,496 8497 ],498 [499 4,500 9501 ],502 [503 1,504 10505 ],506 [507 6,508 11509 ],510 [511 7,512 12513 ],514 [515 9,516 13517 ],518 [519 12,520 14521 ],522 [523 0,524 15525 ],526 [527 11,528 16529 ],530 [531 15,532 17533 ],534 [535 17,536 18537 ]538 ]539 ],540 "output": 13239291355541 },542 {543 "input": [544 [545 758447137,546 880113334,547 787117314,548 856409518,549 206165459,550 211673441,551 263751924,552 50113537,553 365786360,554 973281897,555 802884572,556 115956002,557 959594603,558 369557175,559 466404199560 ],561 527701175,562 [563 [564 0,565 1566 ],567 [568 1,569 2570 ],571 [572 0,573 3574 ],575 [576 3,577 4578 ],579 [580 4,581 5582 ],583 [584 3,585 6586 ],587 [588 0,589 7590 ],591 [592 4,593 8594 ],595 [596 0,597 9598 ],599 [600 0,601 10602 ],603 [604 3,605 11606 ],607 [608 5,609 12610 ],611 [612 5,613 13614 ],615 [616 9,617 14618 ]619 ]620 ],621 "output": 9227506124622 },623 {624 "input": [625 [626 51048371,627 621626174,628 853340026,629 830724220630 ],631 40294959,632 [633 [634 0,635 1636 ],637 [638 1,639 2640 ],641 [642 1,643 3644 ]645 ]646 ],647 "output": 2436397713648 },649 {650 "input": [651 [652 767012436,653 885436648,654 428157424,655 175690002,656 647025660657 ],658 936546775,659 [660 [661 0,662 1663 ],664 [665 1,666 2667 ],668 [669 2,670 3671 ],672 [673 0,674 4675 ]676 ]677 ],678 "output": 4111543332679 },680 {681 "input": [682 [683 856753637,684 507824822,685 132625986686 ],687 384817920,688 [689 [690 0,691 1692 ],693 [694 0,695 2696 ]697 ]698 ],699 "output": 1497204445700 }701 ],702 "haskell_template": "maximumValueSum :: [Int] -> Int -> [[Int]] -> Int\nmaximumValueSum nums k edges ",703 "ocaml_template": "let maximumValueSum (nums: int list) (k: int) (edges: int list list) : int = ",704 "scala_template": "def maximumValueSum(nums: List[Int],k: Int,edges: List[List[Int]]): Int = { \n \n}",705 "java_template": "class Solution {\n public long maximumValueSum(int[] nums, int k, int[][] edges) {\n \n }\n}",706 "python_template": "class Solution(object):\n def maximumValueSum(self, nums, k, edges):\n \"\"\"\n :type nums: List[int]\n :type k: int\n :type edges: List[List[int]]\n :rtype: int\n \"\"\"\n "707}