审题

第一遍读题：所有人行道都要清理

第二遍读题：噢，所有人行道组成一棵树

所以说题目就是在一棵有 $n$ 个点的树上找出两条途径（见 oi-wiki）使得它们可以覆盖所有边。

分析

先考虑只有一个吹雪机的情况。

首先假设吹雪机的起点和终点在同一个点，每条边都要走两遍，$ans = \Sigma\ d \times 2$。当然我们不会这么走，毕竟从起点 $s$ 到终点 $t$ 的路径只需要走一次就够，$ans = (\Sigma\ d \times 2) - dis(s,t)$。

现在考虑有两个吹雪机的情况。

这只是把开始的一条路径换成了两条不交的路径，$ans = (\Sigma\ d \times 2) - dis(s_1,t_1) - dis(s_2,t_2)$。（如果两条路径相交减去的 dis 就会算重）。

我们认为思路对了，考虑做法（这不显然是树 dp 吗，bushi）

令这棵树以点 $1$ 为根，设：

• $f_{u,0}$ 表示在节点 $u$ 的子树中选出两条不交的路径的最长长度。
• $f_{u,1}$ 表示在节点 $u$ 的子树中选出两条不交的路径且其中至少一条的一个端点是 $u$ 的最长长度。
• $f_{u,2}$ 表示在节点 $u$ 的子树中选出一条路径的最长长度。
• $f_{u,3}$ 表示在节点 $u$ 的子树中选出一条路径且它的一端为 $u$ 的最长长度。

设节点 $v$ 为节点 $u$ 的一个子节点，$u$ 到 $v$ 的边权为 $c$，转移方程如下：

$f_{u,0} = \max(\{f_{u,0},f_{v,0},f_{u,1} + f_{v,3} + c,f_{u,2} + f_{v,2},f_{u,3} + f_{v,1} + c\});$

$f_{u,1} = \max(\{f_{u,1},f_{v,1} + c,f_{u,2} + f_{v,3} + c,f_{u,3} + f_{v,2}\});$

$f_{u,2} = \max(\{f_{u,2},f_{v,2},f_{u,3} + f_{v,3} + c\});$

$f_{u,3} = \max(f_{u,3},f_{v,3} + c);$

于是 $ans = (\Sigma\ d \times 2) - f_{1,0}$。

代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 1;i <= n;++i)
#define rpt(i,a,n) for(int i = a;i <= n;++i)
#define pre(i,n) for(int i = n;i;--i)
#define repg(i,u) for(int i = head[u];i;i = e[i].nxt)
#define swap(x,y) (x ^= y ^= x ^= y)
#define debug cerr<<"Help!\n"
constexpr int N = 1e5 + 5;
int f[N][4],head[N],tot,n,u,v,c,ans;
struct edge{
	int v,nxt,c;
}e[N<<1];
inline void add(int u,int v,int c){
	e[++tot] = {v,head[u],c};
	head[u] = tot;
}
void dfs(int u,int fa){
	repg(i,u){
		int v = e[i].v,c = e[i].c;
		if(v == fa) continue;
		dfs(v,u);
		f[u][0] = max({f[u][0],f[v][0],f[u][1] + f[v][3] + c,f[u][2] + f[v][2],f[u][3] + f[v][1] + c});
		f[u][1] = max({f[u][1],f[v][1] + c,f[u][2] + f[v][3] + c,f[u][3] + f[v][2]});
		f[u][2] = max({f[u][2],f[v][2],f[u][3] + f[v][3] + c});
		f[u][3] = max(f[u][3],f[v][3] + c);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	rep(i,n - 1) cin>>u>>v>>c,add(u,v,c),add(v,u,c),ans += c;
	dfs(1,0),ans <<= 1;
	cout<<ans - f[1][0];
	cerr<<'\n'<<1.0 * clock() / CLOCKS_PER_SEC;
	return 0;
}