Submission #538038

#	Time	Username	Problem	Language	Result	Execution time	Memory
538038		zaneyu	Paths (RMI21_paths)	C++14	100 / 100	409 ms	23716 KiB

Main

/*input
3 1
1 2 10
2 3 9
*/
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define MNTO(x,y) x=min(x,y)
#define MXTO(x,y) x=max(x,y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define ld long double
#define sz(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define pii pair<ll,int>
#define f first
#define s second
#define pb push_back
const int maxn=1e5+5;
vector<pii> v[maxn];
int k;
multiset<ll> ms;
multiset<ll,greater<ll>> ls;
ll s=0;
void add(ll x){
    ms.insert(x);
    s+=x;
    if(sz(ms)>k){
        ll z=*ms.begin();
        s-=z;
        ms.erase(ms.begin());
        ls.insert(z);
    }
}
void remove(ll x){
    auto it=ms.find(x);
    if(it==ms.end()){
        ls.erase(ls.find(x));
    }
    else{
        s-=x;
        ms.erase(it);
        if(sz(ls)){
            ll z=(*ls.begin());
            s+=z;
            ms.insert(z);
            ls.erase(ls.begin());
        }
    }
}
ll mx[maxn];
void dfs(int u,int p){
    for(auto x:v[u]){
        if(x.f==p) continue;
        dfs(x.f,u);
        remove(mx[x.f]);
        add(mx[x.f]+x.s);
        MXTO(mx[u],mx[x.f]+x.s);
    }
    add(0);
}
ll ans[maxn];
void dfs2(int u,int p){
    vector<pii> asd;
    asd.pb({0,u});
    for(auto x:v[u]){
        asd.pb({mx[x.f]+x.s,x.f});
    }
    ans[u]=s;
    sort(ALL(asd)),reverse(ALL(asd));
    for(auto x:v[u]){
        if(x.f==p) continue;
        ll tmp=mx[u];
        mx[u]=asd[0].f;
        if(x.f==asd[0].s){
            mx[u]=asd[1].f;
        }
        remove(mx[x.f]+x.s);
        add(mx[x.f]);
        add(mx[u]+x.s);
        remove(mx[u]);
        dfs2(x.f,u);
        remove(mx[x.f]);
        add(mx[x.f]+x.s);
        remove(mx[u]+x.s);
        add(mx[u]);
        mx[u]=tmp;
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n;
    cin>>n>>k;
    REP(i,n-1){
        int a,b,c;
        cin>>a>>b>>c;
        --a,--b;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    dfs(0,-1);
    dfs2(0,-1);
    REP(i,n) cout<<ans[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