제출 #1266401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266401		lioow	Paths (RMI21_paths)	C++20	100 / 100	246 ms	15960 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;

const int maxn=100000;
vector<pii>adj[maxn+2];
int dp[maxn+2],dp2[maxn+2];
multiset<int>sisa,utama;
int n,k,jaw[maxn+2],ans=0;
void ins(int x){
    if(x==0) return;
    if((int)utama.size()<k) utama.insert(x),ans+=x;
    else {
        if(*utama.begin()<x){
            sisa.insert(*utama.begin());
            ans-=*utama.begin();
            utama.erase(utama.begin());
            utama.insert(x);
            ans+=x;
        } else {
            sisa.insert(x);
        }
    }
}

void del(int x){
    if(x==0) return;
    if((int)utama.size()<k){
        ans-=x;
        utama.erase(utama.find(x));
    } else {
        if(*utama.begin()<=x){
            ans-=x;
            utama.erase(utama.find(x));
            if(sisa.empty()) return;
            ans+=*sisa.rbegin();
            utama.insert(*sisa.rbegin());
            sisa.erase(sisa.find(*sisa.rbegin()));
        } else {
            sisa.erase(sisa.find(x));
        }
    }
}

void dfs(int x,int p){
    dp[x]=0;
    dp2[x]=0;
    for(auto v:adj[x]){
        if(v.fi==p) continue;
        dfs(v.fi,x);
        if(dp[x]<dp[v.fi]+v.se){
            ins(dp[x]);
            dp2[x]=dp[x];
            dp[x]=dp[v.fi]+v.se;
        } else {
            ins(dp[v.fi]+v.se);
            if(dp[v.fi]+v.se>dp2[x]) dp2[x]=dp[v.fi]+v.se;
        }
    }
}

void dfs2(int x,int p){
    jaw[x]=ans;
    for(auto v:adj[x]){
        if(v.fi==p) continue;
        int a=dp[x];
        if(dp[v.fi]+v.se==dp[x]) a=dp2[x];
        int b=dp[v.fi];
        if(a+v.se>dp[v.fi]){
            dp2[v.fi]=dp[v.fi];
            dp[v.fi]=a+v.se;
        } else {
            dp2[v.fi]=max(dp2[v.fi],a+v.se);
        }
        del(b+v.se);
        ins(b);
        del(a);
        ins(a+v.se);

        dfs2(v.fi,x);

        ins(b+v.se);
        del(b);
        ins(a);
        del(a+v.se);
    }
}

signed main() {
	cin>>n>>k;
    for(int i=1;i<=n-1;i++){
        int u,v,w;cin>>u>>v>>w;
        adj[u].push_back({v,w});adj[v].push_back({u,w});
    }
    dfs(1,-1);
    ins(dp[1]);
    jaw[1]=ans;
    dfs2(1,-1);
    for(int i=1;i<=n;i++) cout<<jaw[i]<<endl;
}

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