154912025-02-19 22:45:04GervidLogisztikai központcpp17Accepted 50/5098ms15756 KiB
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <limits.h>

using namespace std;
using ll = long long;

vector<vector<array<ll, 2>>> g;
vector<ll> maxdist, secondmaxdist;
vector<array<ll, 2>> maxneighbour;

void max_distance_update(int node, array<ll, 2> neighbour)
{
	ll dist = (maxneighbour[neighbour[0]][0] == node ? secondmaxdist[neighbour[0]] : maxdist[neighbour[0]]);
	if (maxdist[node] < dist + neighbour[1])
	{
		secondmaxdist[node] = maxdist[node];
		maxdist[node] = dist + neighbour[1];
		maxneighbour[node] = neighbour;
	}
	else secondmaxdist[node] = max(secondmaxdist[node], dist + neighbour[1]);
}

void gather(int node, int parent)
{
	for (array<ll, 2> neighbour : g[node])
	{
		if (neighbour[0] == parent) continue;
		gather(neighbour[0], node);
		max_distance_update(node, neighbour);
	}
}

void distribute(int node, array<ll, 2> parent)
{
	if (parent[0] != -1) max_distance_update(node, parent);
	for (array<ll, 2> neighbour : g[node])
	{
		if (neighbour[0] == parent[0]) continue;
		distribute(neighbour[0], { node, neighbour[1] });
	}
}

int descent(int node, int parent)
{
	if (maxneighbour[node][0] == parent || maxdist[maxneighbour[node][0]] > maxdist[node]) return node;
	return descent(maxneighbour[node][0], node);
}

vector<int> ans;

void fill(int node, int parent)
{
	ans.push_back(node);
	for (array<ll, 2> neighbour : g[node])
	{
		if (neighbour[0] == parent) continue;
		if (maxdist[neighbour[0]] == maxdist[node])
		{
			fill(neighbour[0], node);
		}
	}
}

int main()
{
	iostream::sync_with_stdio(0);
	cin.tie(0);

	int n, i;
	cin >> n;

	g.resize(n);
	for (i = 0; i < n-1; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		g[--a].push_back({ --b, c });
		g[b].push_back({ a, c });
	}

	maxdist.resize(n, 0), secondmaxdist.resize(n, 0), maxneighbour.resize(n), ans.reserve(n);
	gather(0, -1);
	distribute(0, { -1, -1 });
	fill(descent(0, -1), -1);
	cout << maxdist[ans[0]] << '\n' << ans.size() << '\n';
	
	sort(ans.begin(), ans.end());
	for (i = 0; i < ans.size(); i++) cout << ans[i] + 1 << ' ';
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms316 KiB
2Accepted0/079ms9752 KiB
3Accepted4/41ms316 KiB
4Accepted4/41ms316 KiB
5Accepted4/41ms316 KiB
6Accepted4/41ms316 KiB
7Accepted4/41ms316 KiB
8Accepted5/52ms316 KiB
9Accepted2/298ms10972 KiB
10Accepted2/286ms10908 KiB
11Accepted2/21ms316 KiB
12Accepted2/22ms564 KiB
13Accepted2/24ms820 KiB
14Accepted2/27ms1332 KiB
15Accepted2/275ms9932 KiB
16Accepted2/283ms9524 KiB
17Accepted2/281ms10372 KiB
18Accepted2/264ms7692 KiB
19Accepted2/275ms10400 KiB
20Accepted3/397ms15756 KiB