#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 3e5 + 5;
int n, k;
ll mx[MAXN], res[MAXN], cur[MAXN];
pair <ll, int> dp[MAXN];
vector <pair <int, ll> > Adj[MAXN];
void DFS(int node, int p = -1)
{
for(auto x : Adj[node])
{
if(x.first == p)
{
continue;
}
DFS(x.first, node);
dp[x.first].first += x.second;
dp[node] = max(dp[node], dp[x.first]);
}
if(dp[node].second == 0)
{
dp[node] = make_pair(0, node);
}
}
ll ans;
set <pair <ll, int> > First, Last;
void Add(pair <ll, int> P)
{
cur[P.second] = P.first;
if((int)First.size() < k)
{
ans += P.first;
First.insert(P);
}
else
{
pair <ll, int> tmp = *First.begin();
if(tmp.first > P.first)
{
Last.insert(P);
}
else
{
First.erase(First.begin());
ans -= tmp.first;
First.insert(P);
ans += P.first;
Last.insert(tmp);
}
}
}
void Sub(pair <ll, int> P)
{
if(Last.count(P))
{
Last.erase(P);
}
else
{
ans -= P.first;
// cout << P.first << 'T' << P.second << endl;
// assert(First.count(P));
First.erase(P);
if(!Last.empty())
{
ans += (*Last.rbegin()).first;
First.insert(*Last.rbegin());
Last.erase(*Last.rbegin());
}
}
}
void Print()
{
for(auto x : First)
{
cout << x.first << ' ' << x.second << endl;
}
cout << "owo" << endl;
for(auto x : Last)
{
cout << x.first << ' ' << x.second << endl;
}
cout << endl;
}
void Reroot(int node, int p = -1, pair <ll, int> Good = make_pair(-1, -1))
{
Print();
res[node] = ans;
vector <pair <ll, int> > tmp;
vector <pair <ll, int> > Pref;
vector <pair <ll, int> > Suff;
for(int i = 0; i < (int)Adj[node].size(); i++)
{
int x = Adj[node][i].first;
if(x == p)
{
tmp.push_back(Good);
}
else
{
tmp.push_back(dp[x]);
}
Pref.emplace_back(max(i == 0 ? make_pair(-1ll, -1ll) : Pref[i - 1], tmp[i]));
}
Suff.resize((int)Pref.size());
for(int i = (int)Adj[node].size() - 1; i >= 0; i--)
{
Suff[i] = max((i + 1 == (int)Adj[node].size()) ? make_pair(-1ll, -1ll) : Suff[i + 1], tmp[i]);
}
for(int i = 0; i < (int)Adj[node].size(); i++)
{
int x = Adj[node][i].first;
if(x == p)
{
continue;
}
pair <ll, int> tmp = make_pair(-1, 0);
if(Adj[node].size() == 1)
{
tmp = make_pair(0, node);
}
if(i)
{
tmp = max(tmp, Pref[i - 1]);
}
if(i + 1 != (int)Adj[node].size())
{
tmp = max(tmp, Suff[i + 1]);
}
Sub(tmp);
Add(make_pair(tmp.first + Adj[node][i].second, tmp.second));
Sub(dp[x]);
Add(make_pair(dp[x].first - Adj[node][i].second, dp[x].second));
Reroot(x, node, make_pair(tmp.first + Adj[node][i].second, tmp.second));
Sub(make_pair(tmp.first + Adj[node][i].second, tmp.second));
Add(tmp);
Sub(make_pair(dp[x].first - Adj[node][i].second, dp[x].second));
Add(dp[x]);
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i = 1; i < n; i++)
{
int u, v, c;
cin >> u >> v >> c;
Adj[u].emplace_back(v, c);
Adj[v].emplace_back(u, c);
}
DFS(1);
for(int i = 1; i <= n; i++)
{
mx[dp[i].second] = max(mx[dp[i].second], dp[i].first);
}
for(int i = 1; i <= n; i++)
{
if((int)Adj[i].size() == 1)
{
Add(make_pair(mx[i], i));
}
}
Reroot(1);
for(int i = 1; i <= n; i++)
{
cout << res[i] << '\n';
}
}
Compilation message
Main.cpp: In function 'void Reroot(int, int, std::pair<long long int, int>)':
Main.cpp:113:38: error: operands to '?:' have different types 'std::pair<long long int, long long int>' and '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, int> >, std::pair<long long int, int> >::value_type' {aka 'std::pair<long long int, int>'}
113 | Pref.emplace_back(max(i == 0 ? make_pair(-1ll, -1ll) : Pref[i - 1], tmp[i]));
Main.cpp:113:38: note: and each type can be converted to the other
Main.cpp:118:56: error: operands to '?:' have different types 'std::pair<long long int, long long int>' and '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, int> >, std::pair<long long int, int> >::value_type' {aka 'std::pair<long long int, int>'}
118 | Suff[i] = max((i + 1 == (int)Adj[node].size()) ? make_pair(-1ll, -1ll) : Suff[i + 1], tmp[i]);
Main.cpp:118:56: note: and each type can be converted to the other
