| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1213600 | Muhammad_Aneeq | Paths (RMI21_paths) | C++20 | 0 ms | 0 KiB |
#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];
multiset<long long>*vl[N]={};
long long dist[N]={};
long long dp[N][2]={};
long long ans[N]={};
int lv=0;
void dfs(int u,int p=0)
{
bool w=1;
for (auto [i,c]:nei[u])
{
if (i==p) continue;
w=0;
dist[i]=dist[u]+c;
dfs(i,u);
}
vl[u]=new multiset<long long>();
if (w)
(*vl[u]).insert(dist[u]-dist[p]);
else
{
int v=-1,sz=0;
for (auto [i,c]:nei[u])
{
if (i==p) continue;
if ((*vl[i]).size()>sz)
{
sz=(*vl[i]).size();
v=i;
}
}
vl[u]=vl[v];
for (auto [i,c]:nei[u])
{
if (i==v||i==p) continue;
for (auto j:(*vl[i]))
(*vl[u]).insert(j);
}
long long z=*rbegin(*vl[u]);
(*vl[u]).erase((*vl[u]).find(z));
z+=dist[u]-dist[p];
(*vl[u]).insert(z);
}
}
void ud(int u,int p=0)
{
for (auto [i,c]:nei[u])
{
if (i==p) continue;
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);
}
}
inline void solve()
{
int n,k;
cin>>n>>k;
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;
}
for (int i=1;i<=n;i++)
{
dist[i]=0;
dfs(i);
int z=min(int((*vl[i]).size()),k);
long long ans=0;
while (z--)
{
long long f=*rbegin(*vl[i]);
(*vl[i]).erase((*vl[i]).find(f));
ans+=f;
}
cout<<ans<<endl;
}
}
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();
}
}