Submission #878329

#TimeUsernameProblemLanguageResultExecution timeMemory
878329Mr_PhPaths (RMI21_paths)C++17
0 / 100
41 ms23376 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace std; using namespace __gnu_pbds; template<class x> using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>; ll mod=(ll)1e9+7; ll mod1=998244353; ///the defines :) #define endl '\n' #define vi vector<int> #define ent(arr) for(int i=0;i<arr.size();i++)cin>>arr[i]; #define all(arr) arr.begin(),arr.end() #define allr(arr) arr.rbegin(),arr.rend() #define sz size() #define int long long vector<vector<pair<int,int>>>adj; int n,k; int length[200002]; pair<int,int> ans[2][20002]; pair<int,int>dfs(int node,int parent,int w) { // cout<<"HI"<<endl; pair<int,int>xd= {0,0}; for(auto i:adj[node]) { if(i.first==parent) continue; pair<int,int>mx=dfs(i.first,node,i.second); // mx.first+=w; pair<int,int>mx1=mx; mx1=ans[0][i.first]; mx1.first+=i.second; if(mx>ans[0][node]) ans[1][node]=max(ans[0][node],ans[1][i.first]),ans[0][node]=mx1; else ans[1][node]=max(mx1,ans[1][node]); xd=max(xd,mx); } if(adj[node].sz==1) { length[node]=w; ans[0][node]= {0,node}; return {w,node}; } length[ans[0][node].second]+=w; xd.first+=w; //ans[0][node].first+=w; return xd; } ordered_set<pair<int,int>>st; int lol; int fans[200002]; void re(int x) { int pog=st.order_of_key({length[x],x}); if(pog>=k)lol-=length[x]; st.erase({length[x],x}); } void add(int x,bool del) { st.insert({length[x],x}); int pog=st.order_of_key({length[x],x}); if(del){ if(pog>=k) lol+=length[x]; else lol+=(*st.find_by_order(k)).first; } else{ if(pog>=k) { lol+=length[x]; if(k>0) lol-=(*st.find_by_order(k-1)).first; } } } void dfs1(int node,int parent,int w,pair<int,int>prv) { if(parent!=0){ prv.first+=w; int pog=st.order_of_key({length[ans[0][node].second],ans[0][node].second}); re(ans[0][node].second); length[ans[0][node].second]-=w; add(ans[0][node].second,pog>=k); fans[node]=lol; } for(auto i:adj[node]) { if(i.first==parent)continue; pair<int,int>nxt=prv; if(ans[0][i.first].second==ans[0][node].second) nxt=max(ans[1][node],nxt); else nxt=max(ans[0][node],nxt); int pog=st.order_of_key({length[nxt.second],nxt.second}); re(nxt.second); length[nxt.second]+=i.second; add(nxt.second,pog>=k); dfs1(i.first,node,i.second,nxt); pog=st.order_of_key({length[nxt.second],nxt.second}); re(nxt.second); length[nxt.second]-=i.second; add(nxt.second,pog>=k); } if(parent!=0){ int pog=st.order_of_key({length[ans[0][node].second],ans[0][node].second}); re(ans[0][node].second); length[ans[0][node].second]+=w; add(ans[0][node].second,pog>=k); } } void preprocess() {} void solve() { cin>>n>>k; adj.resize(n+1); for(int i=0; i<n-1; i++) { int a,b,c; cin>>a>>b>>c; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } dfs(1,0,0); for(int i=1; i<=n; i++) st.insert({length[i],i}); int cnt=0; k=max(0ll,(int)st.sz-k); for(auto i:st) { if(cnt>=k) lol+=i.first; cnt++; } fans[1]=lol; dfs1(1,0,0,{0,0}); for(int i=1;i<=n;i++)cout<<fans[i]<<endl; } signed main() { // freopen("meta_game_input.txt","r",stdin); // freopen("otput.txt","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); preprocess(); //bla(); int t=1; //cin>>t; while(t--) 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...