aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-02-23 21:59:21 -0700
committerJack Sangdahl <[email protected]>2025-02-23 21:59:21 -0700
commitf86f165d87dacea43fb73a7f4106b3e3dbc3d83e (patch)
treea41296e9c82098eeaec929d4265422f6a184076f
parentd938f644a2885ebd6b39d8339f7422454fc7e956 (diff)
downloadleetcode-f86f165d87dacea43fb73a7f4106b3e3dbc3d83e.tar.gz
leetcode-f86f165d87dacea43fb73a7f4106b3e3dbc3d83e.zip
2467. most profitable path in a tree
-rw-r--r--most_profitable_path_tree.c113
-rw-r--r--most_profitable_path_tree.py58
2 files changed, 171 insertions, 0 deletions
diff --git a/most_profitable_path_tree.c b/most_profitable_path_tree.c
new file mode 100644
index 0000000..458a21d
--- /dev/null
+++ b/most_profitable_path_tree.c
@@ -0,0 +1,113 @@
+// 2467. Most Profitable Path in a Tree
+#include "leetcode.h"
+
+/*
+ * there is an undirected tree with 'n' nodes labeled from 0 to 'n - 1', rooted
+ * at node 0. you are given a 2d integer array 'edges' of length 'n - 1' where
+ * 'edges[i] = [a_i, b_i]' indicates that there is an edge between nodes 'a_i'
+ * and 'b_i' in the tree. at every node 'i', there is a gate. you are also given
+ * an array of even integers 'amount', where 'amount[i]' represents the price
+ * needed to open the gate at node 'i', if 'amount[i]' is negative, or the case
+ * reward obtained on oening the gate at node 'i' otherwise. return the maximum
+ * net income alice can have if she travels towards the optimal leaf node.
+ */
+
+#define HIGH 100100
+#define PASS 100010
+
+struct node {
+ int val;
+ struct node *next;
+};
+
+struct head {
+ struct node *head;
+};
+
+struct node *push_node(int val) {
+ struct node *new = (struct node *)malloc(sizeof(struct node));
+ new->val = val;
+ new->next = NULL;
+ return new;
+}
+
+void connect_edges(struct head *graph, int v1, int v2) {
+ struct node *tmp = push_node(v2);
+ tmp->next = graph[v1].head;
+ graph[v1].head = tmp;
+ tmp = push_node(v1);
+ tmp->next = graph[v2].head;
+ graph[v2].head = tmp;
+}
+
+struct head *create_graph(int **edges, int edgesSize) {
+ struct head *graph =
+ (struct head *)calloc(edgesSize + 1, sizeof(struct head));
+ for (int i = 0; i < edgesSize; i++)
+ connect_edges(graph, edges[i][0], edges[i][1]);
+ return graph;
+}
+
+bool bob_traverse(struct head *graph, int *vis, int curr) {
+ if (!curr)
+ return true;
+ struct node *new = graph[curr].head;
+ while (new) {
+ if (vis[new->val] == HIGH) {
+ vis[new->val] = vis[curr] + 1;
+ if (bob_traverse(graph, vis, new->val))
+ return true;
+ vis[new->val] = PASS;
+ }
+ new = new->next;
+ }
+ return false;
+}
+
+void alice_traverse(struct head *graph, int *alice_vis, int *bob_vis,
+ int *amount, int curr, int sum, int *max) {
+ if (bob_vis[curr] > alice_vis[curr])
+ sum += amount[curr];
+ else if (bob_vis[curr] == alice_vis[curr])
+ sum += amount[curr] / 2;
+ struct node *new = graph[curr].head;
+ bool leaf = true;
+ while (new) {
+ if (alice_vis[new->val] == HIGH) {
+ leaf = false;
+ alice_vis[new->val] = alice_vis[curr] + 1;
+ alice_traverse(graph, alice_vis, bob_vis, amount, new->val, sum, max);
+ }
+ new = new->next;
+ }
+ if (leaf)
+ *max = *max > sum ? *max : sum;
+}
+
+int mostProfitablePath(int **edges, int edgesSize, int *edgesColSize, int bob,
+ int *amount, int amountSize) {
+ int *bob_vis = (int *)malloc((edgesSize + 1) * sizeof(int));
+ int *alice_vis = (int *)malloc((edgesSize + 1) * sizeof(int));
+ int max = INT_MIN;
+ for (int i = 0; i <= edgesSize; i++)
+ bob_vis[i] = alice_vis[i] = HIGH;
+ struct head *graph = create_graph(edges, edgesSize);
+ bob_vis[bob] = alice_vis[0] = 0;
+ bob_traverse(graph, bob_vis, bob);
+ alice_traverse(graph, alice_vis, bob_vis, amount, 0, 0, &max);
+ return max;
+}
+
+int main() {
+ int e1i[4][2] = {{0, 1}, {1, 2}, {1, 3}, {3, 4}}, a1[] = {-2, 4, 2, -4, 6};
+ int e2i[1][2] = {{0, 1}}, a2[] = {-7280, 2350};
+ struct two_d_arr e1, e2;
+ two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
+ two_d_arr_init(&e2, ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i);
+ printf("%d\n", mostProfitablePath(e1.arr, e1.row_size, e1.col_size, 3, a1,
+ ARRAY_SIZE(a1))); // expect: 6
+ printf("%d\n", mostProfitablePath(e2.arr, e2.row_size, e2.col_size, 1, a2,
+ ARRAY_SIZE(a2))); // expect: -7280
+ two_d_arr_free(&e1);
+ two_d_arr_free(&e2);
+}
diff --git a/most_profitable_path_tree.py b/most_profitable_path_tree.py
new file mode 100644
index 0000000..c419a13
--- /dev/null
+++ b/most_profitable_path_tree.py
@@ -0,0 +1,58 @@
+# 2467. Most Profitable Path in a Tree
+
+"""
+there is an undirected tree with 'n' nodes labeled from 0 to 'n - 1', rooted
+at node 0. you are given a 2d integer array 'edges' of length 'n - 1' where
+'edges[i] = [a_i, b_i]' indicates that there is an edge between nodes 'a_i'
+and 'b_i' in the tree. at every node 'i', there is a gate. you are also given
+an array of even integers 'amount', where 'amount[i]' represents the price
+needed to open the gate at node 'i', if 'amount[i]' is negative, or the case
+reward obtained on oening the gate at node 'i' otherwise. return the maximum
+net income alice can have if she travels towards the optimal leaf node.
+"""
+
+
+class Solution(object):
+ def mostProfitablePath(self, edges, bob, amount):
+ """
+ :type edges: List[List[int]]
+ :type bob: int
+ :type amount: List[int]
+ :rtype: int
+ """
+ n = len(edges) + 1
+ graph = [[] for i in range(n)]
+ vis = [0] * n
+ for i, j in edges:
+ graph[i].append(j)
+ graph[j].append(i)
+
+ def dfs(i, v):
+ vis[i] = 1
+ res = -float("inf")
+ db = 0 if i == bob else n
+ for j in graph[i]:
+ if vis[j]:
+ continue
+ cur, kk = dfs(j, v + 1)
+ res = max(res, cur)
+ db = min(db, kk)
+ if res == -float("inf"):
+ res = 0
+ if v == db:
+ res += amount[i] // 2
+ if v < db:
+ res += amount[i]
+ return res, db + 1
+
+ return dfs(0, 0)[0]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.mostProfitablePath(
+ edges=[[0, 1], [1, 2], [1, 3], [3, 4]], bob=3, amount=[-2, 4, 2, -4, 6]
+ )
+ )
+ print(obj.mostProfitablePath(edges=[[0, 1]], bob=1, amount=[-7280, 2350]))