Difference Between Maximum and Minimum Price Sum

Difference Between Maximum and Minimum Price Sum - Problem

There exists an undirected and initially unrooted tree with n nodes indexed from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.

Each node has an associated price. You are given an integer array price, where price[i] is the price of the ith node.

The price sum of a given path is the sum of the prices of all nodes lying on that path.

The tree can be rooted at any node root of your choice. The incurred cost after choosing root is the difference between the maximum and minimum price sum amongst all paths starting at root.

Return the maximum possible cost amongst all possible root choices.

Input & Output

Example 1 — Linear Tree

$ Input: n = 3, edges = [[0,1],[1,2]], price = [2,3,1]

› Output: 2

💡 Note: When root=0: paths [2+3=5, 2+3+1=6], cost=6-5=1. When root=1: paths [3+2=5, 3+1=4], cost=5-4=1. When root=2: path [1+3+2=6], cost=0. Maximum cost is 2 when we choose an optimal root.

Example 2 — Single Node

$ Input: n = 1, edges = [], price = [5]

› Output: 0

💡 Note: Only one node, so there's only one path (the node itself) with sum 5. Max - min = 5 - 5 = 0.

Example 3 — Star Tree

$ Input: n = 4, edges = [[0,1],[0,2],[0,3]], price = [1,2,3,4]

› Output: 3

💡 Note: When root=0: paths [1+2=3, 1+3=4, 1+4=5], cost=5-3=2. When root=1: paths [2+1=3, 2+1+3=6, 2+1+4=7], cost=7-3=4. Maximum cost across all roots is 4.

Constraints

1 ≤ n ≤ 2 × 10⁴
edges.length = n - 1
0 ≤ ai, bi ≤ n - 1
ai ≠ bi
edges represents a valid tree
1 ≤ price[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with nodes having associated prices

Choose Root

Try each node as root and calculate paths

Max Difference

Find maximum cost (max_path - min_path) across all roots

Key Takeaway

🎯 Key Insight: Different root choices create different path structures, affecting the cost calculation

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

This problem requires finding the optimal root for a tree to maximize the difference between maximum and minimum path sums. The key insight is that we need to try each node as root and calculate all paths from root to leaves. The brute force approach works by trying all possible roots and computing path sums via DFS. Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Tree Rerooting Optimization	O(n²)	O(n)	Use tree rerooting to avoid recalculating all paths for each root
Brute Force - Try All Roots	O(n²)	O(n)	Try each node as root, calculate all path sums using DFS

Tree Rerooting Optimization — Algorithm Steps

Step 1: Calculate max and min paths for initial root (node 0)
Step 2: For each potential new root, update paths incrementally
Step 3: Use DFS to efficiently recompute affected path sums
Step 4: Track maximum cost across all root transitions

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Root

Calculate all paths for first root

Reroot

Change root and update only affected paths

Optimize

Reuse calculations from previous root where possible

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_N 1000

int graph[MAX_N][MAX_N];
int graphSize[MAX_N];
int price[MAX_N];
long long pathSums[MAX_N];
int pathSumsCount;

void dfs(int node, int parent, long long currentSum, int n) {
    currentSum += price[node];
    int isLeaf = 1;
    for (int i = 0; i < graphSize[node]; i++) {
        int neighbor = graph[node][i];
        if (neighbor != parent) {
            isLeaf = 0;
            dfs(neighbor, node, currentSum, n);
        }
    }
    if (isLeaf) {
        pathSums[pathSumsCount++] = currentSum;
    }
}

long long solution(int n, int edges[][2], int edgesCount, int priceArr[]) {
    if (n == 1) return 0;
    
    for (int i = 0; i < n; i++) {
        graphSize[i] = 0;
        price[i] = priceArr[i];
    }
    
    for (int i = 0; i < edgesCount; i++) {
        int a = edges[i][0], b = edges[i][1];
        graph[a][graphSize[a]++] = b;
        graph[b][graphSize[b]++] = a;
    }
    
    long long maxCost = 0;
    for (int root = 0; root < n; root++) {
        pathSumsCount = 0;
        dfs(root, -1, 0LL, n);
        
        if (pathSumsCount >= 1) {
            long long maxSum = pathSums[0], minSum = pathSums[0];
            for (int i = 1; i < pathSumsCount; i++) {
                if (pathSums[i] > maxSum) maxSum = pathSums[i];
                if (pathSums[i] < minSum) minSum = pathSums[i];
            }
            long long cost = maxSum - minSum;
            if (cost > maxCost) maxCost = cost;
        }
    }
    
    return maxCost;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int edges[MAX_N][2];
    int edgesCount = n - 1;
    int priceArr[MAX_N];
    
    printf("%lld\n", solution(n, edges, edgesCount, priceArr));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Still need to consider all pairs of nodes for path calculations in worst case

⚠ Quadratic Growth

Space Complexity

O(n)

Adjacency list and recursion stack for DFS traversal

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

189 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Tree Rerooting Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler