Tap here to switch tabs
Problem
Submissions

Problem: Maximum Score After Applying Operations on a Tree

Maximum Score After Applying Operations on a Tree gives a rooted tree with node values. Choose nodes to zero out for points while keeping every root-to-leaf path's remaining sum positive.

Statement

There is an undirected tree with nn nodes labeled from 00 to n−1n - 1, rooted at node 00. You are given a 22D integer array edges of length n−1n - 1, where edges[i] = [ai,bi][a_i, b_i] indicates an edge between nodes aia_i and bib_i. You are also given a 00 indexed integer array values of length nn, where values[i] represents the value associated with the ith node.

You start with a score of 00. In each operation, you can choose any node i, add values[i] to your score, and set values[i] to 00.

The tree is considered healthy if the sum of node values along every path from the root node to any leaf node is strictly greater than 00.

Return the maximum score you can achieve while keeping the tree healthy.

Constraints:

  • 2≤n≤2×1042 \leq n \leq 2 \times 10^4

  • edges.length =n−1= n - 1

  • edges[i].length =2= 2

  • 0≤ai,bi<n0 \leq a_i, b_i < n

  • values.length =n= n

  • 1≤1 \leq values[i] ≤109\leq 10^9

  • The input is generated such that edges represents a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Score After Applying Operations on a Tree

Maximum Score After Applying Operations on a Tree gives a rooted tree with node values. Choose nodes to zero out for points while keeping every root-to-leaf path's remaining sum positive.

Statement

There is an undirected tree with nn nodes labeled from 00 to n−1n - 1, rooted at node 00. You are given a 22D integer array edges of length n−1n - 1, where edges[i] = [ai,bi][a_i, b_i] indicates an edge between nodes aia_i and bib_i. You are also given a 00 indexed integer array values of length nn, where values[i] represents the value associated with the ith node.

You start with a score of 00. In each operation, you can choose any node i, add values[i] to your score, and set values[i] to 00.

The tree is considered healthy if the sum of node values along every path from the root node to any leaf node is strictly greater than 00.

Return the maximum score you can achieve while keeping the tree healthy.

Constraints:

  • 2≤n≤2×1042 \leq n \leq 2 \times 10^4

  • edges.length =n−1= n - 1

  • edges[i].length =2= 2

  • 0≤ai,bi<n0 \leq a_i, b_i < n

  • values.length =n= n

  • 1≤1 \leq values[i] ≤109\leq 10^9

  • The input is generated such that edges represents a valid tree.