Tap here to switch tabs
Problem
Submissions

Problem: Choose Edges to Maximize Score in a Tree

Choose Edges to Maximize Score in a Tree asks you to select edges from a weighted rooted tree so that no two share a node, then return the maximum sum of their weights.

Statement

You are given a weighted tree consisting of nn nodes labeled from 00 to n−1n - 1, rooted at node 00. The tree is represented by a 00 indexed 22D integer array edges of length nn, where edges[i] = [par_i, weight_i] indicates that node par_i is the parent of node i with an edge weight of weight_i. For the root node 00, edges[0] = [-1, -1].

You want to select a subset of edges such that no two chosen edges share a common node.

Return the maximum possible sum of weights among the chosen edges.

Constraints:

  • n == edges.length

  • 1≤1 \leq n ≤105\leq 10^5

  • edges[i].length ==2== 2

  • par_0 ==== weight_0 ==−1== -1

  • 0≤0 \leq par_i ≤\leq n −1- 1 for all i≥1i \geq 1

  • par_i ≠\neq i

  • −106≤-10^6 \leq weight_i ≤106\leq 10^6 for all i≥1i \geq 1

  • edges represents a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Choose Edges to Maximize Score in a Tree

Choose Edges to Maximize Score in a Tree asks you to select edges from a weighted rooted tree so that no two share a node, then return the maximum sum of their weights.

Statement

You are given a weighted tree consisting of nn nodes labeled from 00 to n−1n - 1, rooted at node 00. The tree is represented by a 00 indexed 22D integer array edges of length nn, where edges[i] = [par_i, weight_i] indicates that node par_i is the parent of node i with an edge weight of weight_i. For the root node 00, edges[0] = [-1, -1].

You want to select a subset of edges such that no two chosen edges share a common node.

Return the maximum possible sum of weights among the chosen edges.

Constraints:

  • n == edges.length

  • 1≤1 \leq n ≤105\leq 10^5

  • edges[i].length ==2== 2

  • par_0 ==== weight_0 ==−1== -1

  • 0≤0 \leq par_i ≤\leq n −1- 1 for all i≥1i \geq 1

  • par_i ≠\neq i

  • −106≤-10^6 \leq weight_i ≤106\leq 10^6 for all i≥1i \geq 1

  • edges represents a valid tree.