Given a tree with N nodes numbered from 1 to N. Each Node has a value denoting the number of points you get when you visit that Node. Each edge has a length and as soon as you travel through this edge number of points is reduced by the length of the edge, the task is to choose two nodes u and v such that the number of points is maximized at the end of the path from node u to node v.
Note: The number of points should not get negative in between the path from node u to node v.
Examples:
Input:
Output: Maximal Point Path in this case will be 2->1->3 and maximum points at the end of path will be (3-2+1-2+3) = 3
Input:
Output: Maximal Point Path in this case will be 2 -> 4 and maximum points at the end of path will be (3-1+5) = 7
Approach: This problem can be solved optimally using DP with trees concept.
Steps to solve the problem:
- Root the tree at any node say (1).
- For each of the nodes v in the tree, find the maximum points of the path passing through the node v. The answer will be the maximum of this value among all nodes in the tree.
- To calculate this value for each node, maintain a dp array, where dp[v] is the maximal points of the path starting at node v for the subtree rooted at node v. dp[v] for a node v can be calculated from points[v] + max(dp[u] – wv->u ) where u is child of node v, wv->u is length of edge connecting node v and u and points[v] is the number points at the node v.
- Now to find the maximum points of the path passing through the node v we calculate dp[u]-wv->u for each child of v and take the two biggest values from it and add points[v] in it.
- If the maximum value of dp[u]-wv->u is negative then we will take 0 instead of it.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;class GFG {public: // Adjacency list to store the edges. vector<vector<pair<int, int> > > adj; // To store maximum points of a path // starting at a node vector<int> dp; // Visited vector to keep trackof nodes for // which dp values has already been calculated vector<int> vis; // To store the final answer int ans = 0; // Function for visiting every node and // calculating dp values for each node. void dfs(int curr_node, vector<int>& points) { // Mark the current node as visited so // that it does not have to be visited again. vis[curr_node] = 1; // To store maximum path starting // at node minus lenght of edge connecting // that node to current node for each // child of current node. vector<int> child_nodes; // Iterating through each child // of current node. for (auto x : adj[curr_node]) { // To check whether the child has been // already visited or not if (!vis[x.first]) { // Call dfs function for the child dfs(x.first, points); } // Push the value(maximum points path // starting at this child node minus lenght // of edge) into the vector child_nodes.push_back(dp[x.first] - x.second); } // Sort the vector in decreasing order // to pick 2 maximum 2 values. sort(child_nodes.begin(), child_nodes.end(), greater<int>()); // max1-to store maximum points path // starting at child node of current // node, max2-to store second maximum // points path starting at child node // of current node. int max1 = 0, max2 = 0; if (child_nodes.size() >= 2) { max1 = max(max1, child_nodes[0]); max2 = max(max2, child_nodes[1]); } else if (child_nodes.size() >= 1) { max1 = max(max1, child_nodes[0]); } // Calculate maximum points path passing // through current node. ans = max(ans, max1 + max2 + points[curr_node]); // Store maximum points path starting // at current node in dp[curr_node] dp[curr_node] = max1 + points[curr_node]; } // To find maximal points path int MaxPointPath(int n, vector<int> points, vector<vector<int> > edges) { adj.resize(n + 1); dp.resize(n + 1); vis.resize(n + 1); // Filling adajency list for (int i = 0; i < n - 1; i++) { adj[edges[i][0]].push_back( { edges[i][1], edges[i][2] }); adj[edges[i][1]].push_back( { edges[i][0], edges[i][0] }); } // Calling dfs for node 1 dfs(1, points); return ans; }};// Driver codeint main(){ GFG obj; // Number of Vertices int n = 5; // Points at each node vector<int> points(n + 1); points[1] = 6; points[2] = 3; points[3] = 2; points[4] = 5; points[5] = 0; // Edges and their lengths vector<vector<int> > edges{ { 1, 2, 10 }, { 2, 3, 3 }, { 2, 4, 1 }, { 1, 5, 11 } }; cout << obj.MaxPointPath(n, points, edges); return 0;} |
Java
import java.util.*;class GFG { // Adjacency list to store the edges. List<List<AbstractMap.SimpleEntry<Integer, Integer>>> adj; // To store maximum points of a path starting at a node List<Integer> dp; // Visited vector to keep track of nodes for // which dp values have already been calculated List<Integer> vis; // To store the final answer int ans = 0; // Constructor GFG() { adj = new ArrayList<>(); dp = new ArrayList<>(); vis = new ArrayList<>(); } // Function for visiting every node and calculating dp values for each node. void dfs(int currNode, List<Integer> points) { // Mark the current node as visited so that it does not have to be visited again. vis.set(currNode, 1); // To store maximum path starting at node minus length of edge connecting that node to the current node for each child of the current node. List<Integer> childNodes = new ArrayList<>(); // Iterating through each child of the current node. for (AbstractMap.SimpleEntry<Integer, Integer> x : adj.get(currNode)) { // To check whether the child has been already visited or not if (vis.get(x.getKey()) == 0) { // Call dfs function for the child dfs(x.getKey(), points); } // Push the value (maximum points path starting at this child node minus length of the edge) into the vector childNodes.add(dp.get(x.getKey()) - x.getValue()); } // Sort the vector in decreasing order to pick 2 maximum 2 values. Collections.sort(childNodes, Collections.reverseOrder()); // max1 - to store the maximum points path starting at the child node of the current node, max2 - to store the second maximum points path starting at the child node of the current node. int max1 = 0, max2 = 0; if (childNodes.size() >= 2) { max1 = Math.max(max1, childNodes.get(0)); max2 = Math.max(max2, childNodes.get(1)); } else if (childNodes.size() == 1) { max1 = Math.max(max1, childNodes.get(0)); } // Calculate maximum points path passing through the current node. ans = Math.max(ans, max1 + max2 + points.get(currNode)); // Store the maximum points path starting at the current node in dp[currNode] dp.set(currNode, max1 + points.get(currNode)); } // To find the maximal points path int maxPointPath(int n, List<Integer> points, List<List<Integer>> edges) { for (int i = 0; i <= n; i++) { adj.add(new ArrayList<>()); dp.add(0); vis.add(0); } // Filling the adjacency list for (List<Integer> edge : edges) { adj.get(edge.get(0)).add(new AbstractMap.SimpleEntry<>(edge.get(1), edge.get(2))); adj.get(edge.get(1)).add(new AbstractMap.SimpleEntry<>(edge.get(0), edge.get(2))); } // Calling dfs for node 1 dfs(1, points); return ans; } // Driver code public static void main(String[] args) { GFG obj = new GFG(); // Number of Vertices int n = 5; // Points at each node List<Integer> points = new ArrayList<>(); points.add(0); // Adding an extra element at index 0 for simplicity points.add(6); points.add(3); points.add(2); points.add(5); points.add(0); // Edges and their lengths List<List<Integer>> edges = Arrays.asList( Arrays.asList(1, 2, 10), Arrays.asList(2, 3, 3), Arrays.asList(2, 4, 1), Arrays.asList(1, 5, 11) ); System.out.println(obj.maxPointPath(n, points, edges)); }} |
Python3
# Python Code Implementationclass GFG: def __init__(self): # Adjacency list to store the edges. self.adj = [] # To store maximum points of a path #starting at a node self.dp = [] # Visited vector to keep track of nodes #for which dp values has already been calculated self.vis = [] # To store the final answer self.ans = 0 # Function for visiting every node and #calculating dp values for each node. def dfs(self, curr_node, points): # Mark the current node as visited so # that it does not have to be visited again. self.vis[curr_node] = 1 # To store maximum path starting at node # minus length of edge connecting that node to # current node for each child of current node. child_nodes = [] # Iterating through each child of current node. for x in self.adj[curr_node]: # To check whether the child # has been already visited or not if not self.vis[x[0]]: # Call dfs function for the child self.dfs(x[0], points) # Push the value(maximum points path # starting at this child node minus length of edge) # into the vector child_nodes.append(self.dp[x[0]] - x[1]) # Sort the vector in decreasing # order to pick 2 maximum values. child_nodes.sort(reverse=True) # max1-to store maximum points path starting # at child node of current node, max2-to store # second maximum points path starting at # child node of current node. max1 = 0 max2 = 0 if len(child_nodes) >= 2: max1 = max(max1, child_nodes[0]) max2 = max(max2, child_nodes[1]) elif len(child_nodes) >= 1: max1 = max(max1, child_nodes[0]) # Calculate maximum points path # passing through current node. self.ans = max(self.ans, max1 + max2 + points[curr_node]) # Store maximum points path starting # at current node in dp[curr_node] self.dp[curr_node] = max1 + points[curr_node] # To find maximal points path def MaxPointPath(self, n, points, edges): self.adj = [[] for _ in range(n + 1)] self.dp = [0] * (n + 1) self.vis = [0] * (n + 1) # Filling adjacency list for i in range(n - 1): self.adj[edges[i][0]].append((edges[i][1], edges[i][2])) self.adj[edges[i][1]].append((edges[i][0], edges[i][2])) # Calling dfs for node 1 self.dfs(1, points) return self.ans# Driver codeif __name__ == "__main__": obj = GFG() # Number of Vertices n = 5 # Points at each node points = [0, 6, 3, 2, 5, 0] # Edges and their lengths edges = [ [1, 2, 10], [2, 3, 3], [2, 4, 1], [1, 5, 11] ] print(obj.MaxPointPath(n, points, edges))# This code is contributed by Sakshi |
C#
//C# code for the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG{ // Adjacency list to store the edges. List<List<Tuple<int, int>>> adj = new List<List<Tuple<int, int>>>(); // To store maximum points of a path // starting at a node List<int> dp = new List<int>(); // Visited vector to keep track of nodes for // which dp values have already been calculated List<bool> vis = new List<bool>(); // To store the final answer int ans = 0; // Function for visiting every node and // calculating dp values for each node. void dfs(int currNode, List<int> points) { // Mark the current node as visited so // that it does not have to be visited again. vis[currNode] = true; // To store maximum path starting // at node minus length of edge connecting // that node to the current node for each // child of the current node. List<int> childNodes = new List<int>(); // Iterating through each child // of the current node. foreach (var edge in adj[currNode]) { int childNode = edge.Item1; int edgeLength = edge.Item2; // To check whether the child has been // already visited or not if (!vis[childNode]) { // Call dfs function for the child dfs(childNode, points); } // Push the value (maximum points path // starting at this child node minus length // of edge) into the list childNodes.Add(dp[childNode] - edgeLength); } // Sort the list in decreasing order // to pick the maximum 2 values. childNodes.Sort((a, b) => b.CompareTo(a)); // max1 - to store maximum points path // starting at a child node of the current // node, max2 - to store the second maximum // points path starting at a child node // of the current node. int max1 = 0, max2 = 0; if (childNodes.Count >= 2) { max1 = Math.Max(max1, childNodes[0]); max2 = Math.Max(max2, childNodes[1]); } else if (childNodes.Count >= 1) { max1 = Math.Max(max1, childNodes[0]); } // Calculate maximum points path passing // through the current node. ans = Math.Max(ans, max1 + max2 + points[currNode]); // Store the maximum points path starting // at the current node in dp[currNode] dp[currNode] = max1 + points[currNode]; } // To find the maximal points path int MaxPointPath(int n, List<int> points, List<List<int>> edges) { adj = new List<List<Tuple<int, int>>>(n + 1); dp = new List<int>(n + 1); vis = new List<bool>(n + 1); for (int i = 0; i <= n; i++) { adj.Add(new List<Tuple<int, int>>()); dp.Add(0); vis.Add(false); } // Filling adjacency list foreach (var edge in edges) { int u = edge[0]; int v = edge[1]; int w = edge[2]; adj[u].Add(new Tuple<int, int>(v, w)); adj[v].Add(new Tuple<int, int>(u, w)); } // Calling dfs for node 1 dfs(1, points); return ans; } static void Main() { GFG obj = new GFG(); // Number of Vertices int n = 5; // Points at each node List<int> points = new List<int>(n + 1) { 0, 6, 3, 2, 5, 0 }; // Edges and their lengths List<List<int>> edges = new List<List<int>> { new List<int> { 1, 2, 10 }, new List<int> { 2, 3, 3 }, new List<int> { 2, 4, 1 }, new List<int> { 1, 5, 11 } }; Console.WriteLine(obj.MaxPointPath(n, points, edges)); }} |
Javascript
// Javascript code for the above approachclass GFG { constructor() { // Adjacency list to store the edges. this.adj = []; // To store maximum points of a path // starting at a node this.dp = []; // Visited vector to keep track of nodes for // which dp values have already been calculated this.vis = []; // To store the final answer this.ans = 0; } // Function for visiting every node and // calculating dp values for each node. dfs(currNode, points) { // Mark the current node as visited so // that it does not have to be visited again. this.vis[currNode] = 1; // To store maximum path starting // at node minus length of edge connecting // that node to the current node for each // child of the current node. const childNodes = []; // Iterating through each child // of the current node. for (const [child, edgeLength] of this.adj[currNode]) { // To check whether the child has been // already visited or not if (!this.vis[child]) { // Call dfs function for the child this.dfs(child, points); } // Push the value (maximum points path // starting at this child node minus length // of the edge) into the vector childNodes.push(this.dp[child] - edgeLength); } // Sort the vector in decreasing order // to pick 2 maximum values. childNodes.sort((a, b) => b - a); // max1 - to store maximum points path // starting at the child node of the current // node, max2 - to store second maximum // points path starting at the child node // of the current node. let max1 = 0, max2 = 0; if (childNodes.length >= 2) { max1 = Math.max(max1, childNodes[0]); max2 = Math.max(max2, childNodes[1]); } else if (childNodes.length >= 1) { max1 = Math.max(max1, childNodes[0]); } // Calculate maximum points path passing // through the current node. this.ans = Math.max(this.ans, max1 + max2 + points[currNode]); // Store maximum points path starting // at the current node in dp[currNode] this.dp[currNode] = max1 + points[currNode]; } // To find maximal points path MaxPointPath(n, points, edges) { this.adj = Array(n + 1).fill().map(() => []); this.dp = Array(n + 1).fill(0); this.vis = Array(n + 1).fill(0); // Filling adjacency list for (let i = 0; i < n - 1; i++) { this.adj[edges[i][0]].push([edges[i][1], edges[i][2]]); this.adj[edges[i][1]].push([edges[i][0], edges[i][2]]); } // Calling dfs for node 1 this.dfs(1, points); return this.ans; }}// Driver codeconst obj = new GFG();// Number of Verticesconst n = 5;// Points at each nodeconst points = [0, 6, 3, 2, 5, 0];// Edges and their lengthsconst edges = [ [1, 2, 10], [2, 3, 3], [2, 4, 1], [1, 5, 11]];console.log(obj.MaxPointPath(n, points, edges));// This code is contributed by ragul21 |
Output
7
Time Complexity: O(n*logn), since for each node sorting is performed on the values of its children.
Auxiliary Space : O(n), where n is the number of nodes in the tree.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
