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; }
page revision: 0, last edited: 24 Jun 2008 13:54