Find the maximum possible value of f(B)
Given a tree rooted at node 1. The tree is given in the form of an array P where Pi denotes the parent of node i, also P1 = -1, as node 1 is the root node. Every node i has a value Ai associated with it. At first, you have to choose any node to start with, after that from a node you can go to any of its child nodes. You’ve to keep moving to a child node until you reach a leaf node. Every time you get to a new node, you write its value. Let us assume that the integer sequence in your path is B. Let us define a function f over B, which is defined as follows: f(B) = B1 – B2 + B3 – B4 + B5… + (-1)(k-1)Bk. You have to find the maximum possible value of f(B).
Examples:
Input: N = 3, A = {1, 2, 3}, P = {-1, 1, 1}
Output: 3
Explanation: The resulting tree is:
1(1)
/ \
2(2) 3(3)
If we choose our starting node as 3, then the resulting sequence will be B = {3}, which will give the maximum possible value.Input: N = 3, A = { 3, 1, 2}, P = {-1, 1, 2}
Output: 4
Explanation: The resulting tree is:
1(3)
|
2(1)
|
3(2)If we choose our starting node as 1, then the resulting sequence will be B = {3, 1, 2}. The value which we’ll get is, 3-1+2 = 4, which is the maximum possible value.
Approach: To solve the problem follow the below idea:
The idea is to use the concept of DFS algorithm and dynamic programming.
Steps to solve this problem:
- Make an adjacency list to store all the edges of the tree.
- We have to take both the cases of a node. If the node contributes to the required path, then the node is adding positive value or negative value. For this we have store all the possibilities in a 2D vector name ans of size 2*N. There are total N nodes. For each node, we have to store both the cases that’s why a 2* sized array is given for all the nodes.
- Also take an vector of size N named leaf to identify if that node is leaf node or not.
- Run a DFS call from the root of the tree. Store the possible answers in ans vector by using the concept of dynamic programming as there can be many sub-problems. Check if that node is leaf or not and store it in leaf array.
- At last, answer will be stored in leaf nodes. So check the ans vector and calculate the answer.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to perform depth-first search (DFS) // and calculate the best node value. void dfs( int u, int p, vector< int > adj[], vector<vector< long long > >& ans, vector< int >& a, vector< bool >& lef) { // Initialize a flag to track if the // current node is a leaf. bool islef = 1; for ( int v : adj[u]) { if (p != v) { // If there's an adjacent node, it's // not a leaf. islef = 0; // Calculate the maximum // value if we choose the // current node. ans[v][0] = max({ ans[v][0], ans[u][1] + a[v] }); // Calculate the maximum // value if we skip the // current node. ans[v][1] = max({ ans[v][1], ans[u][0] - a[v] }); // Recursively traverse the tree. dfs(v, u, adj, ans, a, lef); } } // Set the leaf flag for the current node. lef[u] = islef; } // Function to find the best node value. long long bestNode( int n, vector< int >& A, vector< int >& P) { // Create a 2D vector to store the // maximum values for each node. vector<vector< long long > > v( n, vector< long long >(2, -1e18)); // Initialize the vector with the // values of nodes. for ( int i = 0; i < n; i++) { v[i][0] = A[i]; } // Adjust the parent indices to be zero-based. for ( int & i : P) i--; vector< int > adj[n]; for ( int i = 1; i < n; i++) { // Build the adjacency list for the tree. adj[i].push_back(P[i]); adj[P[i]].push_back(i); } // Create a vector to store // whether each node is a leaf. vector< bool > lef(n, 0); // Start DFS from the root node. dfs(0, -1, adj, v, A, lef); // Initialize the best node value // to a large negative value. long long ans = -1e18; for ( int i = 0; i < n; i++) { if (lef[i]) // Calculate the best node value // by considering all cases. ans = max({ ans, v[i][0], v[i][1] }); } // Return the best node value. return ans; } // Drivers code int main() { int N = 3; vector< int > A = { 1, 2, 3 }; vector< int > P = { -1, 1, 1 }; long long bestNodeValue = bestNode(N, A, P); // Function Call cout << "The best node value: " << bestNodeValue << endl; return 0; } |
Java
import java.util.ArrayList; public class Main { // Function to perform depth-first search (DFS) // and calculate the best node value. static void dfs( int u, int p, ArrayList<Integer>[] adj, long [][] ans, ArrayList<Integer> a, boolean [] lef) { // Initialize a flag to track if the // current node is a leaf. boolean isLeaf = true ; for ( int v : adj[u]) { if (p != v) { // If there's an adjacent node, it's // not a leaf. isLeaf = false ; // Calculate the maximum // value if we choose the // current node. ans[v][ 0 ] = Math.max(ans[v][ 0 ], ans[u][ 1 ] + a.get(v)); // Calculate the maximum // value if we skip the // current node. ans[v][ 1 ] = Math.max(ans[v][ 1 ], ans[u][ 0 ] - a.get(v)); // Recursively traverse the tree. dfs(v, u, adj, ans, a, lef); } } // Set the leaf flag for the current node. lef[u] = isLeaf; } // Function to find the best node value. static long bestNode( int n, ArrayList<Integer> A, ArrayList<Integer> P) { // Create a 2D array to store the // maximum values for each node. long [][] v = new long [n][ 2 ]; // Initialize the array with the // values of nodes. for ( int i = 0 ; i < n; i++) { v[i][ 0 ] = A.get(i); } // Adjust the parent indices to be zero-based. for ( int i = 0 ; i < P.size(); i++) { if (P.get(i) != - 1 ) { P.set(i, P.get(i) - 1 ); } } ArrayList<Integer>[] adj = new ArrayList[n]; for ( int i = 0 ; i < n; i++) { // Build the adjacency list for the tree. adj[i] = new ArrayList<>(); } for ( int i = 1 ; i < n; i++) { adj[i].add(P.get(i)); adj[P.get(i)].add(i); } // Create an array to store // whether each node is a leaf. boolean [] lef = new boolean [n]; // Start DFS from the root node. dfs( 0 , - 1 , adj, v, A, lef); // Initialize the best node value // to a large negative value. long ans = Long.MIN_VALUE; for ( int i = 0 ; i < n; i++) { if (lef[i]) // Calculate the best node value // by considering all cases. ans = Math.max(ans, Math.max(v[i][ 0 ], v[i][ 1 ])); } // Return the best node value. return ans; } // Driver code public static void main(String[] args) { int N = 3 ; ArrayList<Integer> A = new ArrayList<Integer>(); A.add( 1 ); A.add( 2 ); A.add( 3 ); ArrayList<Integer> P = new ArrayList<Integer>(); P.add(- 1 ); P.add( 1 ); P.add( 1 ); long bestNodeValue = bestNode(N, A, P); // Function Call System.out.println( "The best node value: " + bestNodeValue); } } |
Python3
# Python Implementation: def dfs(u, p, adj, ans, a, lef): islef = True for v in adj[u]: if p ! = v: islef = False ans[v][ 0 ] = max (ans[v][ 0 ], ans[u][ 1 ] + a[v]) ans[v][ 1 ] = max (ans[v][ 1 ], ans[u][ 0 ] - a[v]) dfs(v, u, adj, ans, a, lef) lef[u] = islef def bestNode(n, A, P): v = [[ - 1e18 , - 1e18 ] for _ in range (n)] for i in range (n): v[i][ 0 ] = A[i] for i in range ( len (P)): P[i] - = 1 adj = [[] for _ in range (n)] for i in range ( 1 , n): adj[i].append(P[i]) adj[P[i]].append(i) lef = [ False ] * n dfs( 0 , - 1 , adj, v, A, lef) ans = - 1e18 for i in range (n): if lef[i]: ans = max (ans, v[i][ 0 ], v[i][ 1 ]) return ans N = 3 A = [ 1 , 2 , 3 ] P = [ - 1 , 1 , 1 ] bestNodeValue = bestNode(N, A, P) print ( "The best node value:" , bestNodeValue) # This code is contributed by Tapesh(tapeshdua420) |
C#
using System; using System.Collections.Generic; public class GFG { // Function to perform depth-first search (DFS) // and calculate the best node value. static void Dfs( int u, int p, List< int >[] adj, long [,] ans, List< int > a, bool [] lef) { // Initialize a flag to track if the // current node is a leaf. bool isLeaf = true ; foreach ( int v in adj[u]) { if (p != v) { // If there's an adjacent node, it's // not a leaf. isLeaf = false ; // Calculate the maximum // value if we choose the // current node. ans[v, 0] = Math.Max(ans[v, 0], ans[u, 1] + a[v]); // Calculate the maximum // value if we skip the // current node. ans[v, 1] = Math.Max(ans[v, 1], ans[u, 0] - a[v]); // Recursively traverse the tree. Dfs(v, u, adj, ans, a, lef); } } // Set the leaf flag for the current node. lef[u] = isLeaf; } // Function to find the best node value. static long BestNode( int n, List< int > A, List< int > P) { // Create a 2D array to store the // maximum values for each node. long [,] v = new long [n, 2]; // Initialize the array with the // values of nodes. for ( int i = 0; i < n; i++) { v[i, 0] = A[i]; } // Adjust the parent indices to be zero-based. for ( int i = 0; i < P.Count; i++) { if (P[i] != -1) { P[i] -= 1; } } List< int >[] adj = new List< int >[n]; for ( int i = 0; i < n; i++) { // Build the adjacency list for the tree. adj[i] = new List< int >(); } for ( int i = 1; i < n; i++) { adj[i].Add(P[i]); adj[P[i]].Add(i); } // Create an array to store // whether each node is a leaf. bool [] lef = new bool [n]; // Start DFS from the root node. Dfs(0, -1, adj, v, A, lef); // Initialize the best node value // to a large negative value. long ans = long .MinValue; for ( int i = 0; i < n; i++) { if (lef[i]) // Calculate the best node value // by considering all cases. ans = Math.Max(ans, Math.Max(v[i, 0], v[i, 1])); } // Return the best node value. return ans; } // Driver code public static void Main( string [] args) { int N = 3; List< int > A = new List< int > { 1, 2, 3 }; List< int > P = new List< int > { -1, 1, 1 }; long bestNodeValue = BestNode(N, A, P); // Function Call Console.WriteLine( "The best node value: " + bestNodeValue); } } |
Javascript
function dfs(u, p, adj, ans, a, lef) { // Initialize a flag to track if the current node is a leaf. let isLeaf = true ; for (let v of adj[u]) { if (p !== v) { isLeaf = false ; // Calculate the maximum value if we choose the // current node. ans[v][0] = Math.max(ans[v][0], ans[u][1] + a[v]); // Calculate the maximum value if we skip the // current node. ans[v][1] = Math.max(ans[v][1], ans[u][0] - a[v]); // Recursively traverse the tree. dfs(v, u, adj, ans, a, lef); } } lef[u] = isLeaf; } // Function to find the best node value. function GFG(n, A, P) { let v = Array.from({ length: n }, () => Array(2).fill(-1e18)); // Initialize the array with the // values of nodes. for (let i = 0; i < n; i++) { v[i][0] = A[i]; } P = P.map(i => i - 1); // Build the adjacency list for the tree. let adj = Array.from({ length: n }, () => []); for (let i = 1; i < n; i++) { adj[i].push(P[i]); adj[P[i]].push(i); } // Create an array to store // whether each node is a leaf. let lef = Array(n).fill( false ); // Start DFS from the root node. dfs(0, -1, adj, v, A, lef); let ans = -1e18; for (let i = 0; i < n; i++) { if (lef[i]) { // Calculate the best node value by considering all cases. ans = Math.max(ans, v[i][0], v[i][1]); } } // Return the best node value. return ans; } // Drivers code let N = 3; let A = [1, 2, 3]; let P = [-1, 1, 1]; let bestNodeValue = GFG(N, A, P); console.log( "The best node value:" , bestNodeValue); |
The best node value: 3
Time Complexity: O(N)
Auxiliary Space: O(N)