A - Traveling Salesman on Tree

この問題は、すべての辺の重みの総和を $2$ 倍して、直径を引くことで答えを求めることができます。

証明

この問題の答えは、 $1$ から $N$ の順列 $P$ の隣接 $2$ 項 $(P_i, P_{i + 1})$ の最短距離の総和の最小値になります。

ここで、隣接 $2$ 項の最短距離の総和に $P_1$ と $P_N$ の最短距離を足すと、辺の重みの総和の $2$ 倍に等しくなります。

つまり、答えは辺の重みの総和の $2$ 倍から、ある頂点間の距離の最大値を引くことで得られます。