diff options
author | Jack Sangdahl <[email protected]> | 2025-05-22 19:58:42 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-22 19:58:42 -0600 |
commit | 7c308860a1d9db2d811d89141550010378d19405 (patch) | |
tree | f9895eb0fdc0d05df94018e6443c7409fa2e8f55 | |
parent | 3bf84df609fdf9d975804ababe8aea617791f8b0 (diff) | |
download | leetcode-7c308860a1d9db2d811d89141550010378d19405.tar.gz leetcode-7c308860a1d9db2d811d89141550010378d19405.zip |
3068. find the maximum sum of node values
-rw-r--r-- | find_max_sum_node_val.c | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/find_max_sum_node_val.c b/find_max_sum_node_val.c new file mode 100644 index 0000000..6005bc7 --- /dev/null +++ b/find_max_sum_node_val.c @@ -0,0 +1,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); +} |