Write short, human-like code so that it will not get detected by AI plagiarism and using…
- User
Write short, human-like code so that it will not get detected by AI plagiarism and using exactly these variable names (a, b, c, d, r, s, etc). Use a unique, common approach that’s optimized and free of explanations or comments for the following question: You are given a tree rooted at node 1. The tree is given in form of an array P where Pi denotes the parent of node i, Also P1 =- 1, as 1 is the root node. Every node i has a value Aj 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 fover 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).
Example 1:
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.
Example 2:
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.
Your Task: The task is to complete the function bestNode() which takes an integer N and two integer arrays A, P as input parameters and returns the maximum possible value possible.
Constraints: 1≤ N<105 -105 Ai ≤ 105 -1≤ Pi≤N
class Solution { public: long long bestNode(int N, vector &A, vector &P) { // code here } };
- Assistant
class Solution { public: long long bestNode(int N, vector<int> &A, vector<int> &P) { vector<vector<int>> g(N+1, vector<int>()); for(int i=2;i<=N;i++) g[P[i-1]].push_back(i); long long r = LLONG_MIN; vector<long long> dp1(N+1, 0), dp2(N+1, 0); function<void(int)> dfs = [&](int a) { if(g[a].empty()) { dp1[a]=A[a-1]; dp2[a]=-A[a-1]; } else { dp1[a] = A[a-1]; dp2[a] = -A[a-1]; for(auto b:g[a]){ dfs(b); dp1[a] = max(dp1[a], (long long)A[a-1] + dp2[b]); dp2[a] = max(dp2[a], (long long)(-A[a-1]) + dp1[b]); } } r = max(r, dp1[a]); }; for(int a=1;a<=N;a++) if(P[a-1]==-1){ dfs(a); } return r; } };