HELP Weighted Tree — tree problem

Revision en7, by ShashwatS1, 2019-05-06 12:10:42

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.

Constraints:
0<=K<=1000000
0<=N<=500000
0<=weights<=1000000000

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 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.

Tags #graph, greedy, #dfs and similar, #dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English ShashwatS1 2019-05-06 12:10:42 525
en6 English ShashwatS1 2019-05-06 08:51:55 2 Tiny change: ' \n6 5 3 ' -> ' \n6 3 '
en5 English ShashwatS1 2019-05-06 08:51:08 38
en4 English ShashwatS1 2019-05-06 08:32:13 5
en3 English ShashwatS1 2019-05-06 08:25:27 29 Tiny change: ' question?\n' -> ' question? Plz Help. Thanks in advance.\n'
en2 English ShashwatS1 2019-05-06 08:10:47 147
en1 English ShashwatS1 2019-05-06 08:07:57 2638 Initial revision (published)