出题人题解 | #小A与欧拉路#

原题解链接：https://ac.nowcoder.com/discuss/154293

先考虑回路的情况。由于是一棵树，任两点间路径只有一条，从一条边走到深度更大的点，一定还会从同一条边返回以回到起点或者遍历其他子树，所以每条边需要复制一次，此时答案是边权和的两倍。

不是回路的情况可以减掉从终点回到起点的路径，要让这条路径尽量长，所以长度一定是直径的长度。

答案就是边权和的两倍减去直径长度。

求直径可以树形$DPDP$或者$BFS\mathrm{/}DFSBFS/DFS$两次

复杂度 $O(n)O(n)$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
vector< pair<int, int> > G[MAXN];
long long dp1[MAXN], dp2[MAXN], ans, d;

inline void add(int u, int v, int w) {
  G[u].push_back(make_pair(v, w));
}
inline void dfs(int u, int fa) {
  for (auto &it : G[u]) {
    if (fa == it.first) continue;
    dfs(it.first, u);
    if (dp1[u] < dp1[it.first] + it.second) {
      dp2[u] = dp1[u];
      dp1[u] = dp1[it.first] + it.second;
    }
    else dp2[u] = max(dp2[u], dp1[it.first] + it.second);
  }
  d = max(d, dp1[u] + dp2[u]);
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    add(u, v, w), add(v, u, w);
    ans += w << 1;
  }
  dfs(1, 0);
  cout << ans - d;
  return 0;
}