|
Given a tree containing N nodes in the form of an array P where Pi represents the parent of the i-th node and P1 = -1 as the tree is rooted at node 1. Also given an array vals which consists of the value of the ith node from 1 to N. For each node in the tree find the difference between the maximum and minimum subtree sum.
Examples:
Input: N = 6, par[] = [-1, 1, 1, 2, 2, 4], vals[] = [2, 1, 4, 6, 2, 5]
Output: 10 9 0 0 0 0
Explanation:
- For node 1:- the sum of subtrees are 14 and 4 so the difference between maximum and minimum is 10.
- For node 2:- the difference is 9.
- For nodes with a single child the max and min are the same so the difference is 0.
Nodes with 0 child (leaf nodes) have no subtrees hence their difference is 0.
Input: N = 4, par[] = [-1, 1, 1, 1], vals[] = [1, 2, 3, 4]
Output: 2 0 0 0
Explanation: For node 1 the sum of subtrees are 2, 3 and 4 so the difference between the maximum and minimum is 2.
Approach: This can be solved with the following idea:
Iterating over each node, check with maximum and minimum node value and update the mx and mn value and traverse upto leaf node. Return the difference in ans array.
Below are the steps involved:
- Create a adjancy matrix adj.
- Call the func fun:
- Iterate over each node:
- Update maximum and minimum value for each node.
- Add the sum in total and return the value accordingly.
- Update the difference between mx – mn in ans array.
- Return ans.
Below is the implementation of the code:
C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
long long fun(int i, vector<long long>& ans,
vector<int> adj[], vector<int>& val)
{
long long mx = -1e18 + 0, mn = 1e18 + 0;
long long total = 0;
for (auto it : adj[i]) {
long long find = 0;
find = fun(it, ans, adj, val);
mx = max(mx, find);
mn = min(mn, find);
total += find;
}
if (mx != -1e18 + 0) {
ans[i - 1] = (mx - mn);
}
return total + val[i - 1];
}
vector<long long> differenceTree(int n, vector<int>& par,
vector<int>& vals)
{
vector<int> adj[n + 1];
for (int i = 1; i < n; i++) {
adj[par[i]].push_back(i + 1);
}
vector<long long> ans(n, 0);
fun(1, ans, adj, vals);
return ans;
}
int main()
{
int N = 6;
vector<int> pals = { -1, 1, 1, 2, 2, 4 };
vector<int> vals = { 2, 1, 4, 6, 2, 5 };
vector<long long> ans = differenceTree(N, pals, vals);
for (auto a : ans) {
cout << a << " ";
}
return 0;
}
|
Java
import java.util.*;
class DifferenceTree {
static long fun(int i, List<Long> ans, List<Integer>[] adj, List<Integer> val) {
long mx = Long.MIN_VALUE, mn = Long.MAX_VALUE;
long total = 0;
for (int it : adj[i]) {
long find = fun(it, ans, adj, val);
mx = Math.max(mx, find);
mn = Math.min(mn, find);
total += find;
}
if (mx != Long.MIN_VALUE) {
ans.set(i - 1, mx - mn);
}
return total + val.get(i - 1);
}
static List<Long> differenceTree(int n, List<Integer> par, List<Integer> vals) {
List<Integer>[] adj = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
adj[i] = new ArrayList<>();
}
for (int i = 1; i < n; i++) {
adj[par.get(i)].add(i + 1);
}
List<Long> ans = new ArrayList<>(Collections.nCopies(n, 0L));
fun(1, ans, adj, vals);
return ans;
}
public static void main(String[] args) {
int N = 6;
List<Integer> pals = Arrays.asList(-1, 1, 1, 2, 2, 4);
List<Integer> vals = Arrays.asList(2, 1, 4, 6, 2, 5);
List<Long> ans = differenceTree(N, pals, vals);
for (long a : ans) {
System.out.print(a + " ");
}
}
}
|
Python3
def difference_tree(n, par, vals):
adj = [[] for _ in range(n + 1)]
for i in range(1, n):
adj[par[i]].append(i + 1)
ans = [0] * n
def fun(i):
nonlocal ans
mx = float('-inf')
mn = float('inf')
total = 0
for it in adj[i]:
find = fun(it)
mx = max(mx, find)
mn = min(mn, find)
total += find
if mx != float('-inf'):
ans[i - 1] = (mx - mn)
return total + vals[i - 1]
fun(1)
return ans
if __name__ == "__main__":
N = 6
pals = [-1, 1, 1, 2, 2, 4]
vals = [2, 1, 4, 6, 2, 5]
ans = difference_tree(N, pals, vals)
for a in ans:
print(a, end=" ")
|
C#
using System;
using System.Collections.Generic;
class Program
{
static long Fun(int i, List<long> ans, List<List<int>> adj, List<int> val)
{
long mx = long.MinValue, mn = long.MaxValue;
long total = 0;
foreach (int it in adj[i])
{
long find = Fun(it, ans, adj, val);
mx = Math.Max(mx, find);
mn = Math.Min(mn, find);
total += find;
}
if (mx != long.MinValue)
{
ans[i - 1] = (mx - mn);
}
return total + val[i - 1];
}
static List<long> DifferenceTree(int n, List<int> par, List<int> vals)
{
List<List<int>> adj = new List<List<int>>();
for (int i = 0; i <= n; i++)
{
adj.Add(new List<int>());
}
for (int i = 1; i < n; i++)
{
adj[par[i]].Add(i + 1);
}
List<long> ans = new List<long>(new long[n]);
Fun(1, ans, adj, vals);
return ans;
}
static void Main(string[] args)
{
int N = 6;
List<int> pals = new List<int> { -1, 1, 1, 2, 2, 4 };
List<int> vals = new List<int> { 2, 1, 4, 6, 2, 5 };
List<long> ans = DifferenceTree(N, pals, vals);
foreach (long a in ans)
{
Console.Write(a + " ");
}
}
}
|
Javascript
function fun(i, ans, adj, val) {
let mx = -1e18 + 0;
let mn = 1e18 + 0;
let total = 0;
for (let it of adj[i]) {
let find = fun(it, ans, adj, val);
mx = Math.max(mx, find);
mn = Math.min(mn, find);
total += find;
}
if (mx != -1e18 + 0) {
ans[i - 1] = mx - mn;
}
return total + val[i - 1];
}
function differenceTree(n, par, vals) {
let adj = new Array(n + 1).fill().map(() => []);
for (let i = 1; i < n; i++) {
adj[par[i]].push(i + 1);
}
let ans = new Array(n).fill(0);
fun(1, ans, adj, vals);
return ans;
}
function main() {
let N = 6;
let pals = [-1, 1, 1, 2, 2, 4];
let vals = [2, 1, 4, 6, 2, 5];
let ans = differenceTree(N, pals, vals);
for (let a of ans) {
console.log(a + " ");
}
}
main();
|
Time Complexity: O(N)
Auxiliary Space: O(N)
|
