This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 200005
#define ALL(x) x.begin(), x.end()
int n, k, sz[N];
vector<pair<int, int>> g[N];
ll dp[1001][101], dp2[N], dp3[N], dp4[N];
void dfs1(int u, int p)
{
dp[u][0] = dp[u][1] = 0;
sz[u] = 1;
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];
}
void dfs2(int u, int p)
{
dp2[u] = 0;
for (auto [w, v] : g[u]) if (v != p)
{
dfs2(v, u);
if (dp2[v] + w >= dp2[u]) dp3[u] = dp2[u], dp2[u] = dp2[v] + w;
else if (dp2[v] + w >= dp3[u]) dp3[u] = dp2[v] + w;
}
}
void dfs3(int u, int p)
{
for (auto [w, v] : g[u]) if (v != p)
{
if (dp2[v] + w == dp2[u]) dp4[v] = max(dp4[u] + w, dp3[u] + w);
else dp4[v] = max(dp4[u] + w, dp2[u] + w);
dfs3(v, u);
}
}
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 <= 1002)
{
for (int i = 1; i <= n; ++i) cout << oneroot(i) << '\n';
}
else if (n <= 2000)
{
}
else if (k == 1)
{
dfs2(0, 0);
dfs3(0, 0);
for (int i = 1; i <= n; ++i) cout << max(dp2[i], dp4[i]) << '\n';
}
else
{
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |