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<bits/stdc++.h>
#define task "C"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e5 + 5;
const ll INF = 1e18 + 5;
int n, k;
vector<pair<int, int>> Adj[MAXN];
void Input()
{
cin >> n >> k;
for (int i = 1; i < n; i++)
{
int u, v, w;
cin >> u >> v >> w;
Adj[u].pb({v, w});
Adj[v].pb({u, w});
}
}
ll up[MAXN], down[MAXN];
void DFS(int u, int par)
{
for (auto v : Adj[u])
{
if (v.fi == par)
continue;
DFS(v.fi, u);
down[u] = max(down[u], down[v.fi] + v.se);
}
}
multiset<ll> s1, s2;
ll ans = 0;
void add(ll val)
{
s1.insert(val);
ans += val;
if (s1.size() > k)
{
ans -= *s1.begin();
s2.insert(*s1.begin());
s1.erase(s1.begin());
}
}
void del(ll val)
{
if (s1.find(val) != s1.end())
{
ans -= val;
s1.erase(s1.find(val));
if (!s2.empty())
{
ans += *s2.rbegin();
s1.insert(*s2.rbegin());
s2.erase(s2.find(*s2.rbegin()));
}
} else
{
if (s2.find(val) != s2.end())
s2.erase(s2.find(val));
}
}
void DFS1(int u, int par)
{
ll max1 = -INF, max2 = -INF;
int v1, v2;
for (auto v : Adj[u])
{
if (v.fi == par)
continue;
if (max1 < down[v.fi] + v.se)
{
v2 = v1;
max2 = max1;
v1 = v.fi;
max1 = down[v.fi] + v.se;
} else
if (max2 < down[v.fi] + v.se)
{
v2 = v.fi;
max2 = down[v.fi] + v.se;
}
}
for (auto v : Adj[u])
{
if (v.fi == par)
continue;
if (v.fi == v1)
up[v.fi] = max(up[u], max2);
else
up[v.fi] = max(up[u], max1);
up[v.fi] += v.se;
DFS1(v.fi, u);
if (v.fi != v1)
add(down[v.fi] + v.se);
}
}
ll res[MAXN];
void DFS_cal(int u, int par)
{
res[u] = ans;
for (auto v : Adj[u])
{
if (v.fi == par)
continue;
del(up[v.fi] - v.se);
add(up[v.fi]);
del(down[v.fi] + v.se);
add(down[v.fi]);
DFS_cal(v.fi, u);
add(up[v.fi] - v.se);
del(up[v.fi]);
add(down[v.fi] + v.se);
del(down[v.fi]);
}
}
void Solve()
{
DFS(1, 0);
DFS1(1, 0);
add(down[1]);
DFS_cal(1, 0);
for (int i = 1; i <= n; i++)
cout << res[i] << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(task".INP","r"))
{
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
Input();
Solve();
}
Compilation message (stderr)
Main.cpp: In function 'void add(long long int)':
Main.cpp:48:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
48 | if (s1.size() > k)
| ~~~~~~~~~~^~~
Main.cpp: In function 'void DFS1(int, int)':
Main.cpp:78:13: warning: variable 'v2' set but not used [-Wunused-but-set-variable]
78 | int v1, v2;
| ^~
Main.cpp: In function 'int main()':
Main.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | freopen(task".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void DFS1(int, int)':
Main.cpp:100:9: warning: 'v1' may be used uninitialized in this function [-Wmaybe-uninitialized]
100 | if (v.fi == v1)
| ^~
# | 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... |