Maximal Point Path

0 0 11 minutes read

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] – w_v->u) where u is child of node v, w_v->uis 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]-w_v->ufor 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]-w_v->uis 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 code
int 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 Implementation
class 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 code
if __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 approach
using 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 approach
 
class 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 code
const obj = new GFG();
 
// Number of Vertices
const n = 5;
 
// Points at each node
const points = [0, 6, 3, 2, 5, 0];
 
// Edges and their lengths
const 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

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 zambiatek!