Tap here to switch tabs
Problem
Submissions

Problem: Maximum Points After Collecting Coins From All Nodes

Maximum Points After Collecting Coins From All Nodes asks you to harvest a rooted tree in parent order for maximum points, choosing each node's value minus k or half its value, which also halves descendants.

Statement

There is an undirected tree with n nodes rooted at node 00, labeled from 00 to n −1- 1. You are given a 22D integer array edges of length n −1- 1, where edges[i] == [ui,vi][u_i, v_i] denotes an edge between nodes uiu_i and viv_i. You are also given a zero indexed integer array coins of size n, where coins[i] represents the initial number of coins at node i, and an integer k.

You must collect all the coins from every node. You may collect coins from a node only after collecting coins from its parent.

For any node i, you can collect its coins using one of two methods:

  1. Collect coins[i] −k- k points.

  2. Collect ⌊coins[i]/2⌋\lfloor {coins}[i] / 2 \rfloor points. Choosing this method causes the coin count of every node in the subtree rooted at node i to be reduced to ⌊coins[j]/2⌋\lfloor {coins}[j] / 2 \rfloor for every descendant node j.

Return the maximum total points you can collect after harvesting coins from all nodes in the tree.

Constraints:

  • n ==== coins.length

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

  • 0≤0 \leq coins[i] ≤104\leq 10^4

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

  • 0≤0 \leq edges[i][0], edges[i][1] << n

  • 0≤0 \leq k ≤104\leq 10^4

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Points After Collecting Coins From All Nodes

Maximum Points After Collecting Coins From All Nodes asks you to harvest a rooted tree in parent order for maximum points, choosing each node's value minus k or half its value, which also halves descendants.

Statement

There is an undirected tree with n nodes rooted at node 00, labeled from 00 to n −1- 1. You are given a 22D integer array edges of length n −1- 1, where edges[i] == [ui,vi][u_i, v_i] denotes an edge between nodes uiu_i and viv_i. You are also given a zero indexed integer array coins of size n, where coins[i] represents the initial number of coins at node i, and an integer k.

You must collect all the coins from every node. You may collect coins from a node only after collecting coins from its parent.

For any node i, you can collect its coins using one of two methods:

  1. Collect coins[i] −k- k points.

  2. Collect ⌊coins[i]/2⌋\lfloor {coins}[i] / 2 \rfloor points. Choosing this method causes the coin count of every node in the subtree rooted at node i to be reduced to ⌊coins[j]/2⌋\lfloor {coins}[j] / 2 \rfloor for every descendant node j.

Return the maximum total points you can collect after harvesting coins from all nodes in the tree.

Constraints:

  • n ==== coins.length

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

  • 0≤0 \leq coins[i] ≤104\leq 10^4

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

  • 0≤0 \leq edges[i][0], edges[i][1] << n

  • 0≤0 \leq k ≤104\leq 10^4