算法思路

问题分析 :

输入为一棵树（无环连通图），两辆雪铲从起点$S$出发，需覆盖所有边（每条边至少经过一次），求最小总燃料消耗（路径长度之和）。

• 关键性质：
• 每条边必须被清理至少一次，允许重复经过。目标是通过两辆车分担路径，减少重复行走的总距离。

核心思路

$1$. 总边权和
首先计算所有边的长度之和，记为$\text{totalLength}$。

• 若仅一辆车清理所有边，每条边需往返一次（覆盖两次），总距离为$2 \times \text{totalLength}$。
• 两辆车可通过不同路径分担部分边的单次覆盖，减少重复。

$2$. 树的直径
树中最长路径（直径）是优化的关键。两辆车从$S$出发，若能分别走到直径的两个端点，则直径路径只需走一次（无需往返），其余边仍需走两次。

• 第一次DFS：从起点$S$出发，找到距离$S$最远的节点$u$。
• 第二次DFS：从节点$u$出发，找到距离$u$最远的节点$v$，$u$到$v$的距离即为树的直径$d$。

$3$. 最小燃料计算

• 单辆车需走所有边两次，总距离为$2 \times \text{totalLength}$。
• 两辆车通过分担直径路径$d$，使该路径仅需走一次（而非两次），总距离减少$d$。
• 最终公式：
  [ \text{minFuel} = 2 \times \text{totalLength} - d ]

数学推导

• 单辆车覆盖所有边需往返每条边，总距离为$2 \times \text{totalLength}$。
• 两辆车从$S$出发，分别走到直径的两端$u$和$v$，则直径路径$d$只需走一次（两辆车各走一段，无需返回），其余边仍需走两次。
• 重复行走的总距离减少了直径长度$d$，故总燃料消耗为$2 \times \text{totalLength} - d$。

步骤总结

$1$. 输入处理

• 构建树的邻接表，存储每条边的连接节点和长度。
• 计算所有边的长度之和$\text{totalLength}$。

$2$. 两次DFS找直径

• 第一次DFS：从起点$S$出发，遍历树，找到距离$S$最远的节点$u$（记录距离和节点）。
• 第二次DFS：从节点$u$出发，遍历树，找到距离$u$最远的节点$v$，此时$u$到$v$的距离即为树的直径$d$。

$3$. 计算结果

• 根据公式$\text{minFuel} = 2 \times \text{totalLength} - d$，输出最小燃料消耗。

复杂度分析

• 时间复杂度：两次DFS遍历树，每次时间复杂度为$O(N)$（$N$为节点数），总时间复杂度为$O(N)$，适用于$N \leq 10^5$。
• 空间复杂度：邻接表存储树结构，空间复杂度为$O(N)$。

#include <cstdio>
#include <cstring>
using namespace std;
#define maxN 100005
 
int head[maxN], dp[maxN][2];
bool visited[maxN];
int cnt = 0, dmtr = 0;
 
struct Edge {
	int v, w, next;
} edges[maxN - 1];
 
void addEdge(int u, int v, int w) {
	edges[cnt].v = v;
	edges[cnt].w = w;
	edges[cnt].next = head[u];
	head[u] = cnt++;
}
 
void treeDp(int root) {
	visited[root] = true;
	int fstMax = 0, sndMax = 0;
	for (int i = head[root]; i != -1; i = edges[i].next) {
		int v = edges[i].v;
		if (!visited[v]) {
			treeDp(v);
			int curr = dp[v][0] + edges[i].w; 
			if (curr > fstMax) {
				sndMax = fstMax;
				fstMax = curr;
			} else if (curr > sndMax) {
				sndMax = curr;
			}
		}
	}
	dp[root][0] = fstMax;
	dp[root][1] = sndMax;
	if (fstMax + sndMax > dmtr) dmtr = fstMax + sndMax;
}
 
int main(void) {
	int N, start;
	int u, v, w;
	int circum = 0;
	memset(head, -1, sizeof(head));
	memset(visited, 0, sizeof(visited));
	memset(dp, 0, sizeof(dp));
	scanf("%d%d", &N, &start);
	for (int i = 0; i < N - 1; i++) {
		scanf("%d%d%d", &u, &v, &w);
		circum += w;
		addEdge(u, v, w);
		addEdge(v, u, w);
	}
	circum *= 2;
	treeDp(start);
	printf("%d\n", circum - dmtr);
}