【每日一题】小A与欧拉路 题解(树的直径)

Description

小A给你了一棵树，对于这棵树上的每一条边，你都可以将它复制任意（可以为0）次（即在这条边连接的两个点之间再加一条边权相同的边），求所有可能新形成的图中欧拉路的最短长度
欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边只通过恰好一次

Solution

考虑欧拉回路，从哪来回哪去，每条边走两次。现在求欧拉路，因此不用走回来了，于是减去直径的长度就是最优答案。
于是我们可以推出答案为

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
vector<pair<int, int> > G[N];
int p[N];
pair<int, int> dfs(int v, int par = -1, int dist = 0) {
  p[v] = par;
  pair<int, int> res = make_pair(dist, v);
  for(int i = 0; i < G[v].size(); i++) {
    int u = G[v][i].first;
    if(u == par) continue;
    res = max(res, dfs(u, v, dist + G[v][i].second));
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n; cin >> n;
  ll sum = 0;
  for(int i = 1; i <= n - 1; i++) {
    int u, v, w; cin >> u >> v >> w;
    u--, v--;
    G[u].push_back({v, w});
    G[v].push_back({u, w});
    sum += 2 * w;
  }
  pair<int, int> da = dfs(0);
  pair<int, int> db = dfs(da.second);
  cout << sum - db.first << '\n';
  return 0;  
}