All Tracks Algorithms Dynamic Programming Problem

Tree and robots
/

Algorithms, Dynamic Programming, Tree

Problem
Editorial
Analytics

Given an undirected tree with \(n\) vertices. Each edge \(x\) has a cost \(w_x\). The root of the tree is 1.

You have \(m\) robots, each robot starts at root, walks through edges, finally stops at any vertex. When a robot travels through an edge \(x\), you will pay \(w_x\).

You need to make each edge to be visited by at least one robot (can be more than one robot).

Your goal is minimize the cost.

Input

The first line contains two integers, \(n\) and \(m\).

In the next \(n-1\) lines, each line contains three integers, \(u_i,v_i,w_i\), means an edge \((u_i,v_i)\) exists, and the cost is \(w_i\).

It's guaranteed that the given graph is a tree.

Output

An integer representing the minimum cost.

Constraints

\(1 \le n \le 5 \cdot 10^4\)

\(1 \le m \le 50\)

\(1 \le u_i, v_i \le n\)

\(1 \le w_i \le 10^9\)

SAMPLE INPUT
5 3
1 2 8
2 3 3
3 4 14
3 5 7
SAMPLE OUTPUT
39
Explanation

The first robot's route is \(1-2-3-5-3-4\), and the rest two stay at root.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
通知
View All Notifications

?