Balls in Boxes

Metro

Partitions

Codeforces Round 503 (by SIS, Div. 1) B. The hat

Educational Codeforces Round 47 (Rated for Div. 2) E. Intercity Travelling

Codeforces Round 499 (Div. 1) D. Mars rover

Codeforces Round 506 (Div. 3) F. Multicolored Markers

Technocup 2019 - Elimination Round 1 E. Vasya and Good Sequences

Mail.Ru Cup 2018 - Practice Round C. Tanya and Colored Candies

2920. Maximum Points After Collecting Coins From All Nodes

There exists an undirected tree rooted at node 0 with n nodes labeled from 0 to n - 1. You are given 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. You are also given a 0-indexed array coins of size n where coins[i] indicates the number of coins in the vertex i, and an integer k.

Starting from the root, you have to collect all the coins such that the coins at a node can only be collected if the coins of its ancestors have been already collected.

Coins at nodei can be collected in one of the following ways:

• Collect all the coins, but you will get coins[i] - k points. If coins[i] - k is negative then you will lose abs(coins[i] - k) points.
• Collect all the coins, but you will get floor(coins[i] / 2) points. If this way is used, then for all the nodej present in the subtree of nodei, coins[j] will get reduced to floor(coins[j] / 2).

Return the maximum points you can get after collecting the coins from all the tree nodes.