Submission #1244903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244903		AbdullahIshfaq	Paths (RMI21_paths)	C++20	31 / 100	202 ms	17300 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
const int N = 200005;
vector<pair<ll, ll>> g[N];
ll n, k, mx[N], tot = 0, ans[N];
multiset<ll> st;
multiset<ll, greater<ll>> extra;
void push(ll x)
{
	st.insert(x);
	tot += x;
	if (st.size() > k)
	{
		tot -= *st.begin();
		extra.insert(*st.begin());
		st.erase(st.begin());
	}
}

void remove(ll x)
{
	if (st.find(x) != st.end())
	{
		tot -= x;
		st.erase(st.find(x));
		if (!extra.empty())
		{
			tot += *extra.begin();
			st.insert(*extra.begin());
			extra.erase(extra.begin());
		}
	}
	else
	{
		extra.erase(extra.find(x));
	}
}
void dfs1(int u, int v = 0)
{
	bool leaf = 1;
	mx[u] = 0;
	for (auto [i, j] : g[u])
	{
		if (i != v)
		{
			leaf = 0;
			dfs1(i, u);
			push(mx[i] + j);
			remove(mx[i]);
			mx[u] = max(mx[u], mx[i] + j);
		}
	}
	if (leaf)
	{
		push(0);
	}
}
void dfs2(int u, int v = 0)
{
	pair<ll, ll> f = {0, u}, s = {0, u};
	for (auto [i, j] : g[u])
	{
		if (mx[i] + j >= f.first)
		{
			s = f;
			f = {mx[i] + j, i};
		}
		else if (mx[i] + j > s.first)
		{
			s = {mx[i] + j, i};
		}
	}
	ans[u] = tot;
	for (auto [i, j] : g[u])
	{
		if (i != v)
		{
			ll prev = mx[u];
			mx[u] = f.first;
			if (i == f.second)
			{
				mx[u] = s.first;
			}
			push(mx[i]);
			remove(mx[i] + j);

			push(mx[u] + j);
			remove(mx[u]);

			dfs2(i, u);

			push(mx[u]);
			remove(mx[u] + j);

			push(mx[i] + j);
			remove(mx[i]);
			mx[u] = prev;
		}
	}
}
void solve()
{
	ll u, v, w;
	cin >> n >> k;
	for (int i = 1; i < n; i++)
	{
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	dfs1(1);
	dfs2(1);
	for (int i = 1; i <= n; i++)
	{
		cout << ans[i] << '\n';
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll tests = 1;
	// cin >> tests;
	for (int i = 1; i <= tests; i++)
		solve();
}

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