USER
کروکی درون باغ لیکوئید یک درخت سیب دارد. این درخت از پایین به بالا به شکل یک درخت ریشه دار است. راسهای درخت از
0
0 تا
n
−
1
n−1 نام گذاری شدهاند و ریشه این درخت راس
0
0 است. کروکی می داند که درختهای سیب تنها در برگها میوه میدهند. جیاچ به او گفته است که اگر راس
i
i برگ باشد در سال
a
i
a
i
تا سیب می دهد. کروکی میخواهد با قیچی باغبانی خود شاخههایی از درخت را ببرد به صورتی که درخت باقیمانده دقیقا
k
k برگ داشته باشد، شامل راس ریشه باشد و تعداد سیبهایی که در سال می دهد بیشینه باشد. به کروکی کمک کنید که این مقدار بیشینه را بدست آورد.
ﺗﻮجه ﮐﻨﯿﺪ ﮐﻪ راس رﯾﺸﻪ ﺗﻨﻬﺎ در ﺻﻮرتی ﺑﺮگ ﺣﺴﺎب میﺷﻮد ﮐﻪ ﺗﻨﻬﺎ راس ﺑﺎﻗﯿﻤﺎﻧﺪه در درﺧﺖ ﺑﺎﺷﺪ.
ورودی
در ﺳﻄﺮ اول ﺑﻪ ﺗﺮﺗﯿﺐ اﻋﺪاد
n
n و
k
k آمدهاند
در ﺳﻄﺮ دوم
n
n عدد
a
0
,
a
1
,
a
2
,
.
.
.
,
a
n
−
1
a
0
,a
1
,a
2
,...,a
n−1
آمدهاست.
در
i
i امین سطر از
n
−
1
n−1 سطر بعد دو عدد
v
i
v
i
و
u
i
u
i
آمدهاند که نشان دهنده وجود یک شاخه بین راس
v
i
v
i
و
u
i
u
i
در درخت است.
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
تضمین میشود شاخههای ورودی تشکیل یک درخت میدهند.
تضمین می شود درخت در ابتدا حداقل
k
k برگ دارد.
خروجی
در ﺗﻨﻬﺎ ﺳﻄﺮ ﺧﺮوجی، ﺑﯿﺸﺘﺮﯾﻦ ﺗﻌﺪاد ﺳﯿﺒﯽ ﮐﻪ درﺳﺎل میﺗﻮان ﺗﻮﻟﯿﺪ ﮐﺮد را ﭼﺎپ ﮐﻨﯿﺪ.
زیرمسئلهها
زیرمسئله نمره محدودیت
۱ ۱۱
n
≤
20
n≤20
۲ ۱۸
k
≤
2
k≤2
۳ ۲۲
n
≤
500
n≤500
۴ ۴۹ بدون محدودیت اضافی
مثال
ورودی نمونه ۱
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
خروجی نمونه ۱
36
Plain text
ورودی نمونه ۲
3 1
1 2 3
0 1
0 2
Plain text
خروجی نمونه ۲
3
Plain text
ورودی نمونه ۳
3 1
3 2 1
0 1
0 2
Plain text
خروجی نمونه ۳
3
Plain text
ASSISTANT
To solve this problem, we need to use a dynamic programming approach on trees. The goal is to maximize the number of apples collected from exactly `k` leaves after pruning the tree, while ensuring that the tree remains connected and includes the root.
Here's a structured plan to solve the problem:
1. **Tree Representation**:
- We have `n` nodes and `n-1` edges, which form a tree with node `0` as the root.
- Each node `i` can produce `a[i]` apples if it is a leaf.
2. **Dynamic Programming Table**:
- We define `dp[u][l]` as the maximum number of apples we can collect if the subtree rooted at node `u` has exactly `l` leaves.
- Initialize `dp[u][0] = 0` for all nodes `u` because with 0 leaves, no apples can be collected.
- If `u` is a leaf, then `dp[u][1] = a[u]` because there’s only one leaf and the number of apples is `a[u]`.
3. **DFS and DP Transition**:
- Perform a DFS from the root node `0`.
- For each node `u`, iterate over its children `v`.
- Use a temporary DP array to combine results from child `v` back into node `u`.
- For each possible distribution of leaves between the current node and all processed children, update the DP table:
- For each `i` from 0 to `max_leaves`:
- For each child `v`, combine `dp[u][i]` and `dp[v][j]` (for feasible `j`) to update `dp[u][i + j]`.
- This step ensures that for each subtree, we consider every possible count of leaf nodes from all subtrees and update the maximum apples.
4. **Result Extraction**:
- The answer is found in `dp[0][k]`, representing the maximum number of apples you can collect from exactly `k` leaves in the entire tree.
Here is a code implementation in Python, which closely follows this approach:
```python
from collections import defaultdict
import sys
sys.setrecursionlimit(200000)
def dfs(node, parent, k, tree, apples, dp):
dp[node][0] = 0 # With 0 leaves, we can't collect apples
if len(tree[node]) == 1 and node != 0:
# If it's a leaf and not the root itself
dp[node][1] = apples[node]
return
for child in tree[node]:
if child == parent:
continue
dfs(child, node, k, tree, apples, dp)
# Temporary DP array for merging child results
for i in range(k, -1, -1):
best = dp[node][i] # Start with the current best in node
for j in range(k + 1):
if i - j >= 0 and dp[node][i - j] != -1 and dp[child][j] != -1:
best = max(best, dp[node][i - j] + dp[child][j])
dp[node][i] = best
def max_apples(n, k, apples, edges):
tree = defaultdict(list)
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
# Initialize DP table
dp = [[-1] * (k + 1) for _ in range(n)]
# Start DFS from root node 0
dfs(0, -1, k, tree, apples, dp)
# Output the maximum number of apples with exactly k leaves
return dp[0][k]
# Example usage
n = 8
k = 3
apples = [83, 91, 9, 12, 15, 11, 7, 8]
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (3, 5), (4, 6), (4, 7)]
print(max_apples(n, k, apples, edges)) # Output: 36
```
This code implements the dynamic programming approach on trees, solving the problem efficiently for the given constraints. It uses DFS to traverse the tree and update the DP table based on possible leaf configurations, ensuring that the maximum number of apples is collected from exactly `k` leaves.