Submission #1128056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128056		pokmui9909	Paths (RMI21_paths)	C++20	8 / 100	83 ms	14660 KiB

Main

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

#define x first
#define y second

ll N, K, Sum = 0;
priority_queue<ll, vector<ll>, greater<ll>> Q1;
priority_queue<ll, vector<ll>, greater<ll>> E1;
priority_queue<ll> Q2;
priority_queue<ll> E2;

/* void Clean(){
	while(!E1.empty() && E1.top() == Q1.top()) E1.pop(), Q1.pop();
	while(!E2.empty() && E2.top() == Q2.top()) E2.pop(), Q2.pop();
}
void Add(ll v){
	Clean();
	if(v > Q1.top()){
		Sum += -Q1.top() + v;
		Q2.push(Q1.top()); Q1.pop();
		Q1.push(v);
	} else {
		Q2.push(v);
	}
}
void Del(ll v){
	Clean();
	if(v >= Q1.top()){
		Sum += -v + Q2.top();
		E1.push(v);
		Q1.push(Q2.top()); Q2.pop();
	} else {
		E2.push(v);
	}
} */
multiset<ll> S;
void Upd(){
	Sum = 0;
	if(S.empty()) return;
	auto it = prev(S.end());
	for(ll i = 1; i <= K; i++){
		Sum += *it;
		if(it == S.begin()) break;
		it = prev(it);
	}
}
void Add(ll v){
	S.insert(v);
	Upd();
}
void Del(ll v){
	if(v == 0) return;
	assert(S.find(v) != S.end());
	S.erase(S.find(v));
	Upd();
}

ll Rt, D[100005], Sec[100005], F[100005], Go[100005], Ans[100005];
vector<pair<ll, ll>> T[100005];

void cal1(ll u, ll p){
	for(auto e : T[u]){
		if(e.x == p) continue;
		cal1(e.x, u);
		if(D[u] < D[e.x] + e.y){
			Sec[u] = D[u], D[u] = D[e.x] + e.y;
			Go[u] = e.x;
		} else if(Sec[u] < D[e.x] + e.y){
			Sec[u] = D[e.x] + e.y;
		}
	}
	
}
void cal2(ll u, ll p){
	for(auto e : T[u]){
		if(e.x == p) continue;
		if(e.x == Go[u]){
			F[e.x] = max(F[u], Sec[u]) + e.y;
		} else {
			F[e.x] = max(F[u], D[u]) + e.y;
		}
		cal2(e.x, u);
	}
}
void init(ll u, ll p, ll d){
	if(T[u].size() == 1){
		Add(d); return;
	}
	for(auto e : T[u]){
		if(e.x == p) continue;
		if(e.x == Go[u]){
			init(e.x, u, d + e.y);
		} else {
			init(e.x, u, e.y);
		}
	}
}
void dfs(ll u, ll p){
	Ans[u] = Sum;
	for(auto e : T[u]){
		if(e.x == p) continue;
		if(e.x == Go[u]){
			ll up = max(Sec[u], F[u]);
			Del(D[u]); Add(D[u] - e.y);
			Del(up); Add(up + e.y);

			dfs(e.x, u);
			
			Add(D[u]); Del(D[u] - e.y);
			Add(up); Del(up + e.y);
		} else {
			ll up = max(D[u], F[u]);
			Del(D[e.x] + e.y); Add(D[e.x]);
			Del(up); Add(up + e.y);

			dfs(e.x, u);

			Add(D[e.x] + e.y); Del(D[e.x]);
			Add(up); Del(up + e.y);
		}
	}
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> N >> K;
	for(ll i = 1; i <= K; i++){
		Q1.push(0); Q2.push(0);
	}
	for(ll i = 1; i < N; i++){
		ll u, v, c; cin >> u >> v >> c;
		T[u].push_back({v, c});
		T[v].push_back({u, c});
	}
	Rt = 1;
	while(T[Rt].size() == 1) Rt++;
	cal1(Rt, -1); cal2(Rt, -1);
	init(Rt, -1, 0);
	dfs(Rt, -1);
	for(ll i = 1; i <= N; i++){
		cout << Ans[i] << '\n';
	}
}

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