C++14(g++5.4) 解法, 执行用时: 39ms, 内存消耗: 4312K, 提交时间: 2019-03-18 20:21:18

#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
struct node{
	int to,d;
};
vector<node> v[50005];
ll ans=0;
int book[50005];

void dfs(int s,ll dis){
	int len=v[s].size();
	book[s]=1;
	if(len==1&&book[v[s][0].to]==1){
		ans=max(ans,dis);
	}
	for(int i=0;i<len;i++){
		if(book[v[s][i].to]==0){
			dfs(v[s][i].to,dis+v[s][i].d);
		}
	}
}

int main(){
	ll n;
	ll sum=0; 
	scanf("%lld",&n);
	int a,b,c;
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&a,&b,&c);
		v[a].push_back({b,c});
		v[b].push_back({a,c});
		sum+=c;
	}
	dfs(1,0);
	sum=sum*2-ans;
	cout << sum <<endl;
} 

C++ 解法, 执行用时: 29ms, 内存消耗: 4628K, 提交时间: 2022-03-21 10:37:44

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
std::vector<pair<int, int>>G[maxn];
int n, sum;
int dfs(int u, int fa)
{
int res=0;
for(auto&v:G[u])
{
if(v. first==fa) continue;
res=max(res,v. second+dfs(v. first,u));
}
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v,w;scanf("%d%d%d",&u,&v,&w);
G[u]. emplace_back(v,w);
G[v]. emplace_back(u,w);
sum+=w;
}
printf("%d\n",(sum<<1)-dfs(1,0));
return 0;
}