【2020/11/5每日一题】小A与欧拉路

小A与欧拉路
https://ac.nowcoder.com/acm/problem/22618

idea

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

考虑最简单的回路的情况。每条边就一定是经过两次。那么遍历完过后，每条边就需要复制一次。由于不是欧拉回路而是欧拉路径所以可以减去从起点到终点的路径。所以我们要使起点到终点的路径最长。所以问题就是找到树的直径，因此答案就是 ，记得开 。

expand

欧拉路径与欧拉回路

• 欧拉路：一点可经过多次，一边只经过一次，相当于一笔连完。
• 欧拉路径：可以不回到原点。
• 欧拉回路：必须回到原点。

欧拉路

对于无向图，所有边都是连通的。

• 存在欧拉路径的充分必要条件：度数为奇数的点只能有 0 个或者两个。
• 存在欧拉回路的充分必要条件：度数为奇数的点只能有 0 个。

对于有向图，所有边都是连通的。

• 存在欧拉路径的充分必要条件：要么所有点的出度均等于入度；要么除了两个点之外，其余所有点的出度等于入度，剩余的两个点中：一个满足出度比入度多 1（起点），一个满足入度比出度多 1（终点）。

树的直径长度求法

在一棵树中，每一条边都有权值，树中的两个点之间的距离，定义为连接两点的路径上边权之和，那么树上最远的两个点，他们之间的距离，就被称之为，树的直径。别称，树的最长链。

求法：树型

我们假如说，设 号节点为根节点，那么一张 个点， 条边的无向图,我们可以认为它是一棵有根树。我们不妨设 表示从节点 出发，以 为根的子树，能过到达最远节点的距离。也就是对于 节点而言的最长链。

请注意一个点， 为其到达自己子树节点的最长距离，不是到达非子树节点的最长距离.

一个显然的公式就出来了：

也就是说： 节点的最长链 = 一个儿子 节点的最长链，加上 节点到儿子 节点的距离与其本身的值取 。

但是我们知道：树的直径 = 所有上的最长链 + 所有上的次长链

那么此时我们发现，一个非常重要的点，就是： 一定为最长链和次长链或次长链和最长链。

直接上模板：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+20;
int h[N],e[N],ne[N],w[N],idx;
int dis[N],ans;
void dfs(int u, int fa) {
    for(int i=h[u]; i!=-1; i=ne[i]) {
        int x=e[i];//儿子节点
        if (x == fa)//已经访问了，不能再访问了
            continue;
        dfs(x, u);//先处理儿子节点，求出儿子节点的最长链
        ans=max(ans,dis[u]+dis[x]+w[i]);//最长链+次长链
        dis[u]=max(dis[u],dis[x]+w[i]);//更新
    }
}
void init() {
    //自行补充 
}
int main() {
    init();//读入 
    dfs(1, 0);
    return 0;
}

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, M = 4e5 + 10;
int h[N], e[M], ne[M], w[M], idx;
ll dis[N];
ll maxn = -0x3f3f3f3f3f3f3f3f;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int fa) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int x = e[i];
        if (x == fa) continue;
        dfs(x, u);
        maxn = max(maxn, dis[u] + dis[x] + w[i]);
        dis[u] = max(dis[u], dis[x] + w[i]);
    }
}

int main() {
    int n;
    cin >> n;
    ll ans = 0;
    memset(h, -1, sizeof h);
    while (--n) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
        ans += 2 * c;
    }

    dfs(1, 0);
    cout << ans - maxn <<endl;
    return 0;
}