Submission #537665

#TimeUsernameProblemLanguageResultExecution timeMemory
537665siewjhPaths (RMI21_paths)C++17
19 / 100
1095 ms8972 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; typedef long long ll; vector<pair<int, ll>> adjlist[MAXN]; ll dp[MAXN][MAXN]; int nodes, choose; int dfs(int x, int par){ int leaf = 0; dp[x][0] = 0; for (auto nxt : adjlist[x]){ int nn = nxt.first; if (nn == par) continue; leaf += dfs(nn, x); } for (auto nxt : adjlist[x]){ int nn = nxt.first; ll nd = nxt.second; if (nn == par) continue; ll dph[1005]; for (int i = 0; i < 1005; i++) dph[i] = dp[x][i]; for (int i = 1; i <= min(leaf, choose); i++) for (int j = i; j <= min(leaf, choose); j++) dph[j] = max(dph[j], dp[nn][i] + dp[x][j - i] + nd); for (int i = 0; i < 1005; i++) dp[x][i] = dph[i]; } if (leaf == 0) { leaf = 1; dp[x][1] = 0; } return leaf; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> nodes >> choose; for (int i = 1; i < nodes; i++){ int a, b; ll c; cin >> a >> b >> c; adjlist[a].push_back({b, c}); adjlist[b].push_back({a, c}); } for (int i = 1; i <= nodes; i++){ memset(dp, -1, sizeof(dp)); dfs(i, -1); cout << dp[i][choose] << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...