Time limit: 0.5 seconds Memory limit: 256 MB Source: 2nd Preliminary Exam of the 27th…
- User
Time limit: 0.5 seconds Memory limit: 256 MB Source: 2nd Preliminary Exam of the 27th Computer Olympiad Kroki has an apple tree in his Liquid Garden. This tree is shaped like a rooted tree from the bottom up. The vertices of the tree are labeled from 0 0 to n −1 n−1 and the root of this tree is vertex 0 0. Kroki knows that apple trees only bear fruit in leaves. GH has told him that if vertex i i has leaves, it will bear a i a i apples per year. Kroki wants to use his pruning shears to cut branches from the tree so that the remaining tree has exactly k k leaves, including the root vertex, and the number of apples it bears per year is maximum. Help Kroki find this maximum.
Note that a root vertex is considered a leaf only if it is the only remaining vertex in the tree.
Input The first line contains the numbers n n and k k, respectively
The second line n n contains the numbers a 0 , a 1 , a 2 , . . . , a n − 1 a 0 ,a 1 ,a 2 ,...,a n−1 .
In the i ith line of the n − 1 n−1 lines, two numbers v i v i and u i u i appear, indicating the existence of a branch between the vertices v i v i and u i u i in the tree.
1 ≤ n ≤ 100
000 1≤n≤100 000 1 ≤ k ≤ 100 1≤k≤100 1 ≤ a i ≤ 1
000
000
000 1≤a i ≤1 000 000 000 0 ≤v i , u i < n 0≤v i ,u i <n The input branches are guaranteed to form a tree.
The tree is guaranteed to initially have at least k k leaves.
Output Print the maximum number of apples that can be produced in a year on a single line of output.
Subproblems Subproblem Score Constraints 1 11 n ≤ 20 n≤20 2 18 k ≤ 2 k≤2 3 22 n ≤ 500 n≤500 4 49 No additional constraints Example Input sample 1 8 3 83 91 9 12 15 11 7 8 0 1 0 2 1 3 1 4 3 5 4 6 4 7
Plain text Output sample 1 36 Plain text Input sample 2 3 1 1 2 3 0 1 0 2 Plain text Output sample 2 3 Plain text Input sample 3 3 1 3 2 1 0 1 0 2 Plain text Output sample 3 3 c++
- Assistant
To solve this problem, we need to perform dynamic programming (DP) on a rooted tree to maximize the number of apples harvested from exactly
kleaves. The main idea is to traverse the tree in a bottom-up manner (post-order traversal) and calculate for each node the maximum possible apples that can be harvested for every possible number of leaves up tok.Step-by-Step Solution:
-
Tree Representation:
- Represent the tree using an adjacency list. Each node will have a list of its children.
- Identify leaf nodes (nodes with no children).
-
Dynamic Programming (DP) Table:
- Define
dp[u][x]as the maximum number of apples that can be harvested from the subtree rooted at nodeuusing exactlyxleaves. - Initialize
dp[u][1] = a[u]for leaf nodes since making a leaf node itself yieldsa[u]apples.
- Define
-
DP Transition:
- For non-leaf nodes, you have two options:
- Option 1: Make the node itself a leaf. In this case,
dp[u][1] = a[u]. - Option 2: Do not make the node a leaf. Instead, distribute the
xleaves among its children optimally.
- Option 1: Make the node itself a leaf. In this case,
- To handle Option 2, perform a convolution-like process where you combine the results from the children to determine the best possible sum of apples for each possible number of leaves.
- For non-leaf nodes, you have two options:
-
Post-Order Traversal:
- Traverse the tree in post-order (process children before the parent).
- At each node, compute
dp[u][x]based on the children's DP results.
-
Final Result:
- After processing all nodes, the answer will be
dp[0][k], which represents the maximum number of apples that can be harvested from the entire tree with exactlykleaves.
- After processing all nodes, the answer will be
Implementation Considerations:
- Time Complexity: The solution has a time complexity of
O(n * k^2), which is feasible given the constraints (n ≤ 100,000andk ≤ 100). - Memory Optimization: Utilize fixed-size arrays for the DP table to save memory and improve cache performance.
Sample C++ Implementation:
Below is a C++ implementation that follows the above approach. It efficiently computes the required DP table and outputs the maximum number of apples for the given
kleaves.#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll NEG_INF = -1e18; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<ll> a(n); for(auto &x: a) cin >> x; vector<vector<int>> adj(n, vector<int>()); for(int i=0; i<n-1; ++i){ int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } // Build the tree with root 0 // To avoid revisiting parent, use parent array vector<int> parent(n, -1); vector<int> order; // BFS to build post-order queue<int> q; q.push(0); while(!q.empty()){ int u = q.front(); q.pop(); order.push_back(u); for(auto &v: adj[u]){ if(v != parent[u]){ parent[v] = u; q.push(v); } } } // Reverse the order for post-order reverse(order.begin(), order.end()); // Initialize DP table // dp[u][x] = max apples with x leaves in subtree u // Since k <=100, use fixed size // Using a vector of vectors // To save memory and improve cache, use a 1D array // dp[u * (k+1) + x] vector<ll> dp((ll)n * (k+1), NEG_INF); for(auto u: order){ // Find children vector<int> children; for(auto &v: adj[u]){ if(v != parent[u]){ children.push_back(v); } } if(children.empty()){ // Leaf node if(1 <=k){ dp[u*(k+1)+1] = a[u]; } } else{ // Not a leaf // Initialize temporary f[x] vector<ll> f(k+1, NEG_INF); f[0] =0; for(auto &v: children){ // Merge f with dp[v][x] vector<ll> tmp(k+1, NEG_INF); for(int i=0; i<=k; ++i){ if(f[i]==NEG_INF) continue; for(int j=1; j<=k-i; ++j){ if(dp[v*(k+1)+j]==NEG_INF) continue; tmp[i+j] = max(tmp[i+j], f[i] + dp[v*(k+1)+j]); } } // Update f for(int x=0; x<=k; ++x){ f[x] = tmp[x]; } } // Now f[x] contains the max sum for x leaves via children // Option1: make u a leaf: x=1, sum=a[u] // Option2: not make u a leaf: f[x] for(int x=1; x<=k; ++x){ dp[u*(k+1)+x] = f[x]; if(x ==1){ dp[u*(k+1)+x] = max(dp[u*(k+1)+x], a[u]); } } } } ll result = dp[0*(k+1)+k]; cout << result; }Explanation of the Code:
-
Input Reading:
- Read the number of nodes
nand the desired number of leavesk. - Read the array
acontaining the number of apples each node can bear. - Read the edges of the tree and build the adjacency list.
- Read the number of nodes
-
Tree Traversal:
- Perform a BFS to establish parent-child relationships, ensuring we process nodes in post-order.
-
Dynamic Programming:
- Initialize a 1D DP array to simulate a 2D DP table.
- For each node in post-order:
- If it's a leaf, set
dp[u][1]toa[u]. - If it's an internal node, compute the maximum apples by either making it a leaf or distributing the leaves among its children.
- If it's a leaf, set
- Merge the DP results from the children to compute the DP table for the current node.
-
Final Output:
- After processing all nodes, output
dp[0][k], which contains the maximum number of apples that can be harvested with exactlykleaves.
- After processing all nodes, output
Testing the Implementation:
Let's verify the solution with the provided sample inputs.
Sample Input 1:
8 3 83 91 9 12 15 11 7 8 0 1 0 2 1 3 1 4 3 5 4 6 4 7Output:
36Sample Input 2:
3 1 1 2 3 0 1 0 2Output:
3Sample Input 3:
3 1 3 2 1 0 1 0 2Output:
3The implementation correctly computes the maximum number of apples for each sample input, ensuring that exactly
kleaves are selected in the pruned tree. -