#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define int long long
int const N=1e5+10;
vector<pair<int,int>>nei[N];
vector<long long>vl[N]={};
long long dist[N]={};
long long dp[N][2]={};
long long ans[N]={};
int pre[N]={};
int lv=0;
int n,k;
void dfs(int u,int vla=0,int p=0)
{
if (pre[u]==p) return;
pre[u]=p;
bool w=1;
for (auto [i,c]:nei[u])
{
if (i==p) continue;
w=0;
// dist[i]=dist[u]+c;
dfs(i,c,u);
}
vl[u]={};
if (w)
vl[u].push_back(vla);
else
{
for (auto [i,c]:nei[u])
{
if (i==p) continue;
for (auto j:vl[i])
vl[u].push_back(j);
}
sort(begin(vl[u]),end(vl[u]));
vl[u].back()+=vla;
}
}
void ud(int u,int p=0)
{
for (auto [i,c]:nei[u])
{
if (i==p) continue;
ud(i,u);
if (dp[u][0]<dp[i][0]+c)
{
dp[u][1]=dp[u][0];
dp[u][0]=dp[i][0]+c;
}
else if (dp[u][1]<dp[i][0]+c)
dp[u][1]=dp[i][0]+c;
}
}
void bt(int u,long long vl=0,int p=0)
{
ans[u]=max(dp[u][0],vl);
for (auto [i,c]:nei[u])
{
if (i==p) continue;
long long mx=vl;
if (dp[u][0]==dp[i][0]+c)
mx=max(mx,dp[u][1]);
else
mx=max(mx,dp[u][0]);
bt(i,mx+c,u);
}
}
void sol(int u,int p=-1)
{
dfs(u);
int z=min((int)(vl[u]).size(),k);
long long ans1=0;
while (z--)
{
ans1+=vl[u].back();
vl[u].pop_back();
}
ans[u]=ans1;
for (auto [i,c]:nei[u])
if (i!=p)
sol(i,u);
}
inline void solve()
{
cin>>n>>k;
for (int i=1;i<=n;i++)
pre[i]=-1;
for (int i=1;i<n;i++)
{
int u,v,c;
cin>>u>>v>>c;
nei[u].push_back({v,c});
nei[v].push_back({u,c});
}
if (k==1)
{
ud(1);
bt(1);
for (int i=1;i<=n;i++)
cout<<ans[i]<<endl;
return;
}
sol(1);
for (int i=1;i<=n;i++)
cout<<ans[i]<<'\n';
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t=1;
for (int i=1;i<=t;i++)
{
solve();
}
}
# | 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... |