abc 361 E
作者:
Air1222
,
2024-10-02 19:49:41
,
所有人可见
,
阅读 3
//题目描述:n个点,n-1条边,且每个点均联通,寻找从一个点出发,到达所有点所用的最小值
//n个点,n-1条边,且每个点均联通,可以判断为树
//模拟可以得出,每个节点的分支,仅有一条可以不用回归,则要使总代价最小,则应当使得当前不用回归的点最远,即数的直径
//则答案为2*sum(w)-数的直径
#include <iostream>
#include <vector>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<LL,LL>PII;
const int N = 2e5+10;
vector<PII>g[N];
LL d[N];
LL sum;
int c;
void dfs(int u,int father)
{
for(auto k:g[u])
{
if(k.x==father) continue;
d[k.x]=d[u]+k.y;
if(d[k.x]>d[c]) c=k.x;
dfs(k.x,u);
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n-1;i++)
{
int a,b,c;
cin>>a>>b>>c;
sum+=c;
g[a].push_back({b,c});
g[b].push_back({a,c});
}
dfs(1,-1);
d[c]=0;
dfs(c,-1);
cout<<sum*2-d[c];
}