Submission #1130156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130156		mnbvcxz123	Paths (RMI21_paths)	C++20	100 / 100	223 ms	15192 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<ll,ll>;

constexpr int N=1e5+5;
int n,k;
int a[N];
vector<pi>g[N];
ll res[N];
ll mx[N];
multiset<ll>st;
multiset<ll,greater<ll>>ot;

ll cur=0;

void insert(ll x){
    st.insert(x);
    cur+=x;
    if(st.size()>k){
        cur-=*st.begin();
        ot.insert(*st.begin());
        st.erase(st.begin());
    }
}

void erase(ll x){
    auto it=st.find(x);
    if(it!=st.end()){
        cur-=x;
        st.erase(it);
        if(!ot.empty()){
            cur+=*ot.begin();
            st.insert(*ot.begin());
            ot.erase(ot.begin());
        }
    }else ot.erase(ot.find(x));
}

void dfs(int u, int p){
    mx[u]=0;
    bool leaf=1;
    for(const auto&[v,w]:g[u]){
        if(v==p)continue;
        leaf=0;
        dfs(v,u);
        erase(mx[v]);
        insert(mx[v]+w);
        mx[u]=max(mx[u],mx[v]+w);
    }
    if(leaf)insert(0);
}

void reroot(int u, int p){
    pi fi={0,u};
    pi se=fi;
    for(const auto&[v,w]:g[u]){
        if(mx[v]+w>=fi.first){
            se=fi;
            fi={mx[v]+w,v};
        }else if(mx[v]+w>se.first)
            se={mx[v]+w,v};
    }
    res[u]=cur;
    for(const auto&[v,w]:g[u]){
        if(v==p)continue;
        insert(mx[v]);
        erase(mx[v]+w);
        ll roll=mx[u];
        if(v==fi.second)mx[u]=se.first;
        else mx[u]=fi.first;
        insert(mx[u]+w);
        if(mx[u]>0)erase(mx[u]);
        reroot(v,u);
        if(mx[u]>0)insert(mx[u]);
        erase(mx[u]+w);
        mx[u]=roll;
        erase(mx[v]);
        insert(mx[v]+w);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>k;
    for(int i=1,a,b,w;i<n;++i){
        cin>>a>>b>>w;
        g[a].push_back({b,w});
        g[b].push_back({a,w});
    }
    dfs(1,0);
    reroot(1,0);
    for(int i=1;i<=n;++i)cout<<res[i]<<'\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32