Submission #1228718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228718		lopkus	Paths (RMI21_paths)	C++20	68 / 100	1099 ms	164312 KiB

Main

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define int long long
int const N=1e5+10;
vector<pair<int,int>>nei[N];
vector<long long>vl[N]={};
long long dist[N]={};
long long dp[N][2]={};
long long ans[N]={};
int pre[N]={};
int lv=0;
int n,k;
void dfs(int u,int vla=0,int p=0)
{
	if (pre[u]==p) return;
	pre[u]=p;
	bool w=1;
	for (auto [i,c]:nei[u])
	{
		if (i==p) continue;
		w=0;
		// dist[i]=dist[u]+c;
		dfs(i,c,u);
	}
	vl[u]={};
	if (w)
		vl[u].push_back(vla);
	else
	{
		for (auto [i,c]:nei[u])
		{
			if (i==p) continue;
			for (auto j:vl[i])
				vl[u].push_back(j);
		}
		sort(begin(vl[u]),end(vl[u]));
		vl[u].back()+=vla;
	}
}
void ud(int u,int p=0)
{
	for (auto [i,c]:nei[u])
	{
		if (i==p) continue;
		ud(i,u);
		if (dp[u][0]<dp[i][0]+c)
		{
			dp[u][1]=dp[u][0];
			dp[u][0]=dp[i][0]+c;
		}
		else if (dp[u][1]<dp[i][0]+c)
			dp[u][1]=dp[i][0]+c;
	}
}
void bt(int u,long long vl=0,int p=0)
{
	ans[u]=max(dp[u][0],vl);
	for (auto [i,c]:nei[u])
	{
		if (i==p) continue;
		long long mx=vl;
		if (dp[u][0]==dp[i][0]+c)
			mx=max(mx,dp[u][1]);
		else
			mx=max(mx,dp[u][0]);
		bt(i,mx+c,u);
	}
}
void sol(int u,int p=-1)
{
	dfs(u);
	int z=min((int)(vl[u]).size(),k);
	long long ans1=0;
	while (z--)
	{
		ans1+=vl[u].back();
		vl[u].pop_back();
	}
	ans[u]=ans1;
	for (auto [i,c]:nei[u])
		if (i!=p)
			sol(i,u);
}
inline void solve()
{
	cin>>n>>k;
	for (int i=1;i<=n;i++)
		pre[i]=-1;
	for (int i=1;i<n;i++)
	{
		int u,v,c;
		cin>>u>>v>>c;
		nei[u].push_back({v,c});
		nei[v].push_back({u,c});
	}
	if (k==1)
	{
		ud(1);
		bt(1);
		for (int i=1;i<=n;i++)
			cout<<ans[i]<<endl;
		return;
	}
	sol(1);
	for (int i=1;i<=n;i++)
		cout<<ans[i]<<'\n';
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

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