题目
代码
#include <bits/stdc++.h>
using namespace std;
struct ff
{int z,len;
};
vector<ff> vec[300001];
int n,u,v,w,dp[300001][2],ans = 1e9;
void dfs(int x,int fa)
{for(int i = 0;i < vec[x].size();i++){ff son = vec[x][i];if(son.z != fa){dfs(son.z,x);int t = dp[son.z][0] + son.len;if(t > dp[x][0]) swap(t,dp[x][0]);if(t > dp[x][1]) swap(t,dp[x][1]);}}
}
void dfss(int x,int fa)
{for(int i = 0;i < vec[x].size();i++){ff son = vec[x][i];if(son.z != fa){int t;if(dp[x][0] == dp[son.z][0] + son.len) t = dp[x][1] + son.len;else t = dp[x][0] + son.len;if(t > dp[son.z][0]) swap(t,dp[son.z][0]);if(t > dp[son.z][1]) swap(t,dp[son.z][1]);dfss(son.z,x);}}
}
int main()
{cin>>n;for(int i = 1;i < n;i++){cin>>u>>v>>w;vec[u].push_back({v,w});vec[v].push_back({u,w});}dfs(1,0);dfss(1,0);for(int i = 1;i <= n;i++) ans = min(ans,dp[i][0]);for(int i = 1;i <= n;i++)if(ans == dp[i][0])cout<<i<<' '; return 0;
}
