1018
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <math.h>
#include <limits.h>
 
using namespace std;
 
// Datatypes
typedef vector<int> vi; 
typedef vector<string> vs;
typedef vector<vi> vvi; 
typedef pair<int,int> ii; 
typedef long long ll;
typedef long double ld;
 
// Define
#define sz(a)             int((a).size()) 
#define pb                push_back 
#define all(c)            (c).begin(),(c).end() 
#define present(c,x)      ((c).find(x) != (c).end()) 
#define cpresent(c,x)     (find(all(c),x) != (c).end()) 
#define FOR(_i,_n)        for(int (_i) = 0; (_i) < (_n); (_i)++)
#define mp                make_pair
 
// Constants
const double eps = 1e-8; 
const double PI = 3.1415926535897932384626433832795;
 
#define INPUT_FILE "xo.in"
#define OUTPUT_FILE "xo.out"
 
vector< vector<ii> > E;
vector< vector<ii> > EE;
 
int m[200][200] = {0};
int color[200] = {0};
 
void dfs(int u)
{
    color[u] = 1;
    for(int i = 0; i < E[u].size(); i++)
    {
        int v = E[u][i].first;
        if(color[v] == 0)
        {
            dfs(v);
            EE[u].pb(mp(v,E[u][i].second));
        }
    }
}
 
int f(int u, int k)
{
    if(m[u][k] != -1) return m[u][k];
 
    int r = 0;
    int cv = EE[u].size();
 
    if(k == 0)
    {
        r = 0;
    }
    else 
    {
        for(int i = 0; i < EE[u].size(); i++)
        {
            int v = EE[u][i].first;
            int d = EE[u][i].second;
 
            r = max(f(v,k-1) + d, r);
        }
 
        if((k > 1) && (cv > 1)) 
        {
            int dd = EE[u][0].second + EE[u][1].second;
 
            for(int i = 0; i <= k-2; i++)
            {
                r = max(r, dd + f(EE[u][0].first, i) + f(EE[u][1].first, k-2-i));
            }
        }
    }
 
    m[u][k] = r;
 
    return r;
}
 
int main(void)
{
#ifdef ALEX
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    //freopen(INPUT_FILE, "r", stdin);
    //freopen(OUTPUT_FILE, "w", stdout);
#endif
 
    int N,Q;
    cin >> N >> Q;
 
    E.resize(N+1);
    EE.resize(N+1);
 
    for(int i = 0; i < N-1; i++)
    {
        int u,v,d;
        cin >> u >> v >> d;
        E[u].pb(mp(v,d));
        E[v].pb(mp(u,d));
    }
 
    dfs(1);
 
    for(int i = 0; i < 200; i++)
    {
        for(int j = 0; j < 200; j++)
            m[i][j] = -1;
    }
 
    cout << f(1,Q);
 
    return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.