154892025-02-19 22:38:13GervidLogisztikai központcpp17Wrong answer 41/50111ms15624 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;
		if (neighbour[0] == maxneighbour[node][0]) distribute(neighbour[0], { node, neighbour[1] });
		else distribute(neighbour[0], { node, neighbour[1] });
	}
}

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

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);
	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
base41/50
1Accepted0/01ms500 KiB
2Accepted0/079ms9940 KiB
3Accepted4/41ms512 KiB
4Accepted4/41ms316 KiB
5Accepted4/41ms400 KiB
6Accepted4/41ms316 KiB
7Accepted4/41ms316 KiB
8Accepted5/51ms316 KiB
9Accepted2/2100ms10804 KiB
10Accepted2/286ms11064 KiB
11Wrong answer0/21ms316 KiB
12Accepted2/22ms564 KiB
13Accepted2/24ms820 KiB
14Accepted2/27ms1444 KiB
15Accepted2/275ms10036 KiB
16Wrong answer0/286ms9524 KiB
17Accepted2/279ms10292 KiB
18Wrong answer0/270ms7848 KiB
19Accepted2/265ms10540 KiB
20Wrong answer0/3111ms15624 KiB