本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-09 10:29:53

[ABC361E] Tree and Hamilton Path 2
考察：树的直径，dfs，dp。
题目简述：
给定一棵有 $n$ 个点的树，从任意一个点开始，经过所有点后所走过的最短路径。
一个点可以经过多次，最后不一定要回到原点。
数据范围：

• $n\le 2\times 10^5$

考虑下图：

其满足限制的最短路径是 $9\Rightarrow6\Rightarrow1\Rightarrow2\Rightarrow7\Rightarrow2\Rightarrow4\Rightarrow5\Rightarrow8\Rightarrow5\Rightarrow3$，长度为 $4+3+2+5+5+3+5+1+1+4=33$。
我们将其标在树上，就成了下图： 我们发现有向图比原树少了 $3$ 到 $9$ 的这一条路径，而这条路径就是树的直径。
那么我们得出答案就是（设直径为 $len$）： $$\sum_{(u_i,v_i,w_i)\in E}w_i-len$$ 直径采用 dp 就可得到。

代码：

#include<bits\/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i) 
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
#define rpr(i,x,y,z) for(reg int i=x;i<=(y);i+=z)
#define epe(i,x,y,z) for(reg int i=x;i>=(y);i-=z)
#define endl '\n'
#define INF 1e16
#define pb push_back
#define fi first
#define se second
#define lcm(x,y) x\/__gcd(x,y)*y
#define ull unsigned long long
#define prr make_pair
#define pii pair<int,int> 
#define gt(s) getline(cin,s)
#define at(x,y) for(reg auto x:y)
#define ff fflush(stdout)
#define mt(x,y) memset(x,y,sizeof(x))
#define idg isdigit
#define fp(s) string ssss=s;freopen((ssss+".in").c_str(),"r",stdin);freopen((ssss+".out").c_str(),"w",stdout);
#define sstr stringstream 
#define all(x) x.begin(),x.end()
#define mcy(a,b) memcpy(a,b,sizeof(b))
using namespace std;
const int N=2e5+5;
vector<pii >g[N];
int mx[N],mx2[N];
bool vis[N];
inl void dfs(int u,int &num){
	vis[u]=1;
	at(v,g[u])
		if(!vis[v.fi]){
			dfs(v.fi,num);
			if(mx[u]<mx[v.fi]+v.se){
				mx2[u]=mx[u];
				mx[u]=mx[v.fi]+v.se;
			}else mx2[u]=max(mx2[u],mx[v.fi]+v.se);
		}
	num=max(num,mx[u]+mx2[u]);
}
signed main(){
	fst;
	reg int n,num=0,ans=0;
	cin>>n;
	rep(i,2,n){
		reg int u,v,w;
		cin>>u>>v>>w;
		g[u].pb(prr(v,w));
		g[v].pb(prr(u,w));
		ans+=w<<1;
	}
	dfs(1,num);
	cout<<ans-num;
	return 0;
}