Submission #873357

#TimeUsernameProblemLanguageResultExecution timeMemory
873357sleepntsheepPaths (RMI21_paths)C++17
19 / 100
1006 ms32084 KiB
#include <cstdio> #include <cstring> #include <cassert> #include <string> #include <deque> #include <vector> #include <map> #include <queue> #include <algorithm> #include <iostream> #include <utility> using namespace std; using ll = long long; using ld = long double; #define ShinLena cin.tie(nullptr)->sync_with_stdio(false) #define N 2005 #define ALL(x) x.begin(), x.end() int n, k; vector<pair<int, int>> g[N]; ll dp[N][N], sz[N]; void dfs1(int u, int p) { dp[u][0] = 0; sz[u] = 1; dp[u][1] = 0; if (g[u].size() == 1 && u != p) { sz[u] = 1; dp[u][1] = 0; } for (auto [w, v] : g[u]) if (v != p) { dfs1(v, u); for (int i = sz[u]; i >= 0; --i) for (int j = 1; i+j <= k && j <= sz[v]; ++j) dp[u][i+j] = max(dp[u][i+j], dp[u][i] + dp[v][j] + w); sz[u] += sz[v]; } } ll oneroot(int u) { memset(dp, 0xbf, sizeof dp); memset(sz, 0, sizeof sz); dfs1(u, u); return dp[u][k]; } int main() { ShinLena; cin >> n >> k; for (int u, v, w, i = 1; i < n; ++i) cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u); if (n <= 2000) { for (int i = 1; i <= n; ++i) cout << oneroot(i) << '\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...