在上一题树的最长路径上稍微加点东西
- 找到树的最长路径
- 目标点必在该路径的中点附近
- 遍历该路径上的所有点
#include<iostream>
#include<algorithm>
using namespace std;
const int N =100004;
vector<pair<int,int >> t[N];
int n,a,c,b;
int st[N];
int point,maxv=-1;
vector<int> result,fin;
void dfs(int u,int now)
{
if(now>maxv)
{
point =u, maxv = now,fin = result;
}
for(auto i:t[u])
{
int q = i.first;
if(st[q]) continue;
st[q] = true;
result.push_back(now+i.second);
dfs(q,now+i.second);
st[q] = false;
result.pop_back();
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a>>b>>c;
t[a].push_back({b,c});
t[b].push_back({a,c});
}
dfs(1,0);
maxv = 0;
dfs(point ,0);
int last = fin.back();
int ha= 0x3f3f3f3f;
for(auto i:fin)
ha = min(ha,max(last - i,i));
cout<<ha<<endl;
return 0;
}