Submission #871100

#	Time	Username	Problem	Language	Result	Execution time	Memory
871100		MinaRagy06	Paths (RMI21_paths)	C++17	56 / 100	1024 ms	13096 KiB

Main

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

const int N = 100'005;
vector<array<int, 2>> adj[N];
int n, k;
ll vals[N];
pair<ll, int> dp[N][2];
void dfs(int i, int par, int parc) {
	dp[i][0] = dp[i][1] = {-1e18, 0};
	for (auto [nxt, w] : adj[i]) {
		if (nxt == par) continue;
		dfs(nxt, i, w);
		pair<ll, int> nxtval = dp[nxt][0];
		nxtval.first += w;
		if (nxtval > dp[i][1]) {
			dp[i][1] = nxtval;
		}
		if (dp[i][0] < dp[i][1]) {
			swap(dp[i][0], dp[i][1]);
		}
	}
	if (adj[i].size() == 1) {
		dp[i][0] = {0, i};
	}
	vals[dp[i][0].second] += parc;
}
ll ans[N];
ll calc() {
	vector<ll> cur;
	for (int i = 1; i <= n; i++) {
		cur.push_back(vals[i]);
	}
	sort(cur.rbegin(), cur.rend());
	ll sum = 0;
	for (int i = 0; i < k; i++) {
		sum += cur[i];
	}
	return sum;
}
void dfs2(int i, int par, int parc, pair<ll, int> dpup) {
	dpup.first += parc;
	vals[dp[i][0].second] -= parc;
	ans[i] = calc();
	for (auto [nxt, w] : adj[i]) {
		if (nxt == par) continue;
		pair<ll, int> mx = dp[i][0];
		if (dp[i][0].second == dp[nxt][0].second) mx = dp[i][1];
		mx = max(mx, dpup);
		vals[mx.second] += w;
		dfs2(nxt, i, w, mx);
		vals[mx.second] -= w;
	}
	vals[dp[i][0].second] += parc;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	for (int i = 1, u, v, w; i < n; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	dfs(1, 0, 0);
	dfs2(1, 0, 0, {0, 0});
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

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