結果
問題 | No.1488 Max Score of the Tree |
ユーザー |
![]() |
提出日時 | 2021-04-23 21:47:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 1,814 bytes |
コンパイル時間 | 1,149 ms |
コンパイル使用メモリ | 94,448 KB |
最終ジャッジ日時 | 2025-01-20 23:45:19 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> #include <cassert> #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; int n, k; int par[101]; int par_cost[101]; bool used[101]; int ch[101]; struct edge{ int to, cost; }; vector<edge> g[101]; void dfs(int v){ used[v] = true; int cnt = 0; for(edge e : g[v]){ if(!used[e.to]){ par_cost[e.to] = e.cost; par[e.to] = v; dfs(e.to); ch[v] += ch[e.to]; cnt++; } } if(cnt == 0) ch[v] = 1; } using P = pair<ll, int>; ll dp[101][100005]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; cin >> n >> k; for(int i = 0; i < n-1; i++){ int a, b, c; cin >> a >> b >> c; a--; b--; g[a].push_back(edge{b, c}); g[b].push_back(edge{a, c}); } dfs(0); vector<ll> w(n-1), v(n-1); for(int i = 1; i < n; i++){ w[i-1] = par_cost[i]; v[i-1] = par_cost[i]*ch[i]; } for(int i = 0; i < n-1; i++){ for(int j = 0; j <= k; j++){ chmax(dp[i+1][j], dp[i][j]); if(j+w[i] <= k) chmax(dp[i+1][j+w[i]], dp[i][j]+v[i]); } } ll ans = 0; for(int i = 0; i <= k; i++) chmax(ans, dp[n-1][i]); for(int i = 1; i < n; i++){ ans += v[i-1]; } cout << ans << endl; }