Submission #1213629

#TimeUsernameProblemLanguageResultExecution timeMemory
1213629Muhammad_AneeqPaths (RMI21_paths)C++20
68 / 100
1100 ms160668 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]; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...