小A与欧拉路（树直径）

题目：

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

做法：

不难发现每条树边顶多用次，而且路径的起点和终点都是叶子。假如我们确定个叶子作为欧拉路的起终点。那么路径上的边算次，其他边算次。所以我们让这个路径最长，也就是选取树的某条直径端点作为欧拉路的两端，在直径上的边算次贡献，不在则次，就是答案。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
vector<pair<int,int> > g[N];
int rt1, rt2, dis[N], fa[N], mrk[N];
void dfs(int u, int p, int& rt){
    for (auto &pr : g[u]) if (pr.first != p){
        int v = pr.first, w = pr.second;
        fa[v] = u, mrk[v] = w;
        dis[v] = dis[u] + w;
        if (dis[v] > dis[rt]) rt = v;
        dfs(pr.first, u, rt);
    }
}
int main(void){
    IOS;
    int n; cin >> n;
    ll ans = 0;
    for (int i = 0; i < n-1; ++i){
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
        ans += 2*w;
    }
    dfs(1, 0, rt1); dis[rt1] = 0; dfs(rt1, 0, rt2);
    //debug(rt1), debug(rt2);
    while (rt2 != rt1){
        ans -= mrk[rt2], rt2 = fa[rt2];
    }
    cout << ans << endl;
    return 0;
}