4560 2023. 03. 29 17:48:39 horvathabel Logisztikai központ cpp17 Részben helyes 42/50 140ms 41764 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

vector<pair<int,int>> g[100001];
bool seen[100001];
bool seen2[100001];
pair<ll,ll>  mxtav[100001];
ll mxtavvissza[100001];
pair<ll,ll>  mxtav2[100001];
int cnt[100001];
priority_queue<int> q[100001];
ll dfs(int x, int tv){
		seen[x]=true;
		if (cnt[x]==1 && x!=1) return tv; 
		for (pair<int, int> edge:g[x]){
			if (!seen[edge.first]){
								seen[edge.first]=true;

				int v=dfs(edge.first, edge.second); 
				if (v>mxtav[x].first){
					mxtav2[x]=mxtav[x];
					mxtav[x].first=v;
					mxtav[x].second=edge.first; 
				}
				else if (mxtav2[x].first<v){
					mxtav2[x].first=v;
					mxtav2[x].second=edge.first; 
				}
		}
		}
		
	return (mxtav[x].first+tv);
}
void dfs2(int x){
	seen2[x]=true;
	for (pair<int, int> edge:g[x]){
		if (!seen2[edge.first]){
			seen2[edge.first]=true; 
			mxtavvissza[edge.first]=max(mxtavvissza[x]+edge.second,mxtavvissza[edge.first]);
			if (edge.first!=mxtav[x].second) mxtavvissza[edge.first]=max(mxtavvissza[edge.first], mxtav[x].first+edge.second);
			else  mxtavvissza[edge.first]=max(mxtavvissza[edge.first], mxtav2[x].first+edge.second);
			dfs2(edge.first);
		}

	}
}
int main() {
	ll n;
	cin>>n;
	for (int i=0; i<n-1;i++){
		ll x,y,c;
		cin>>x>>y>>c;
		g[x].push_back({y,c});
		g[y].push_back({x,c});
		cnt[x]++;
		cnt[y]++; 
		}
		

	dfs(1,0);
	dfs2(1);
	for (int i=1; i<=n ;i++) mxtav[i].first=max(mxtav[i].first, mxtavvissza[i]);
	vector<ll> ans; 
	ll z=mxtav[1].first; 
	for (int i=2; i<=n;i++){
		if (z>mxtav[i].first){
			z=mxtav[i].first;
			ans.clear();
		}
		if (z==mxtav[i].first) ans.push_back(i);
		
	}
	cout<<z<<endl<<ans.size()<<endl;
	for (int i:ans) cout<<i<<" ";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 42/50
1 Elfogadva 0/0 6ms 12808 KiB
2 Elfogadva 0/0 129ms 27852 KiB
3 Elfogadva 4/4 7ms 13312 KiB
4 Részben helyes 2/4 6ms 13352 KiB
5 Elfogadva 4/4 7ms 13428 KiB
6 Elfogadva 4/4 7ms 13660 KiB
7 Részben helyes 2/4 7ms 13732 KiB
8 Elfogadva 5/5 8ms 13808 KiB
9 Elfogadva 2/2 135ms 30244 KiB
10 Részben helyes 1/2 134ms 30464 KiB
11 Elfogadva 2/2 8ms 14428 KiB
12 Részben helyes 1/2 8ms 14512 KiB
13 Elfogadva 2/2 13ms 15156 KiB
14 Elfogadva 2/2 17ms 16224 KiB
15 Elfogadva 2/2 129ms 29608 KiB
16 Elfogadva 2/2 123ms 28988 KiB
17 Elfogadva 2/2 136ms 30528 KiB
18 Hibás válasz 0/2 103ms 26648 KiB
19 Elfogadva 2/2 133ms 28644 KiB
20 Elfogadva 3/3 140ms 41764 KiB