HELP Weighted Tree — tree problem

Правка en5, от ShashwatS1, 2019-05-06 08:51:08

Given a tree T containing N nodes numbered [1,2..,N] rooted at node 1 . Each edge has a value associated with it.You are also given a number K. You need to find the maximum weight you can collect in K-steps .When you traverse an edge, it is counted as 1 step.

Note:
1. you should start from root node.
2. you can traverse an edge from parent to child or child to parent.
3. you can traverse an edge multiple times.
4. weights of edges are always positive integer.
Input format:

  1. first line contain N,K i.e number of nodes, number of steps respectively.
  2. next N-1 lines contain three integers a,b,c i.e there is an edge between 'a' and 'b' with weight 'c'.

Output format:

maximum weight collected in K-steps.

Example:-
Input:
6 5 3
1 2 5
1 3 6
2 4 15
2 5 1
3 6 11

Output: 35

Explanation:

Traversal for max. weight collection: [1-2-4-2]. Thus weight collected 5+15+15=35

How to solve this question? Plz Help. Thanks in advance.

Теги #graph, greedy, #dfs and similar, #dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский ShashwatS1 2019-05-06 12:10:42 525
en6 Английский ShashwatS1 2019-05-06 08:51:55 2 Tiny change: ' \n6 5 3 ' -> ' \n6 3 '
en5 Английский ShashwatS1 2019-05-06 08:51:08 38
en4 Английский ShashwatS1 2019-05-06 08:32:13 5
en3 Английский ShashwatS1 2019-05-06 08:25:27 29 Tiny change: ' question?\n' -> ' question? Plz Help. Thanks in advance.\n'
en2 Английский ShashwatS1 2019-05-06 08:10:47 147
en1 Английский ShashwatS1 2019-05-06 08:07:57 2638 Initial revision (published)