aboutsummaryrefslogtreecommitdiff
path: root/find_max_sum_node_val.c
blob: 6005bc751056dfd3dbd0251962492e9d9b26505f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 3068. Find the Maximum Sum of Node Values
#include "leetcode.h"

/*
 * 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'. return the maximum possible sum of the values alice
 * can achieve by performing the operation any number of times.
 */

long long maximumValueSum(int *nums, int numsSize, int k, int **edges,
                          int edgesSize, int *edgesColSize) {
  long long ans = 0;
  int u = 1 << 30, v = 0;
  for (int i = 0; i < numsSize; i++) {
    int curr = nums[i] ^ k;
    ans += fmax(nums[i], curr);
    u ^= nums[i] < curr;
    v = fmin(v, abs(nums[i] - curr));
  }
  return ans - u * v;
}

int main() {
  int n1[] = {1, 2, 1}, e1i[2][2] = {{0, 1}, {0, 2}};
  int n2[] = {2, 3}, e2i[1][2] = {{0, 1}};
  int n3[] = {7, 7, 7, 7, 7, 7},
      e3i[5][2] = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}};
  struct two_d_arr e1, e2, e3;
  two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
  two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
  two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
  printf("%lld\n", maximumValueSum(n1, ARRAY_SIZE(n1), 3, e1.arr, e1.row_size,
                                   e1.col_size)); // expect: 6
  printf("%lld\n", maximumValueSum(n2, ARRAY_SIZE(n2), 7, e2.arr, e2.row_size,
                                   e2.col_size)); // expect: 9
  printf("%lld\n", maximumValueSum(n3, ARRAY_SIZE(n3), 3, e3.arr, e3.row_size,
                                   e3.col_size)); // expect: 42
  two_d_arr_free(&e1);
  two_d_arr_free(&e2);
  two_d_arr_free(&e3);
}