算法提高课汇总

理解题意

题目需要我们求所有节点到其他顶点的最大距离, 并取最大距离集合中的最小值.

所以首要任务是求每个顶点到其他点的最大距离, 可以用集合的思路枚举.

$DP$分析

状态表示 $d(u)$&$up(u)$

将顶点$u$到其他点的路径分为两部分:

• 向下走, 其最大值可以用AcWing 1072. 树的最长路径 $dfs$思路求解.

• 向上走, 即$u$先到其父节点$v$, 再加上从$v$到其他节点路径最大值, 也分为两者情况.

  • $v$向上走, 即$w(u, v) + up(v)$.

  • $v$向下, 此时需要考虑$u$向下最大路径是否经过$u$, 若经过, 我们只能退而求其次, 取次大路径,
    若不经过$u$, 则可以取向下的最大路径.

最终对于点$u$, 其到其他节点最大路径为$max\lbrace d1[u], up[u]\rbrace$.

具体实现

实现涉及两个方向的$dfs$:

• 自底向上: 求$u$向下的最大路径, 先计算子节点, 再用子节点值更新父节点.

• 自上向下: 求$u$的子节点$v$向上的最大路径值, 先求$u$的子节点, 再向下求$v$的子节点.

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, M = 2 * N, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], w[M], ne[M], idx;
int d1[N], d2[N], p1[N]; //u向下路径最大值, 次大值, 向下路径最大值经过的子节点
int up[N]; //向上路径的最大值

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

int dfs_d(int u, int father)
{
    d1[u] = d2[u] = -INF;
    for ( int i = h[u]; ~i; i = ne[i] )
    {
        int v = e[i];
        if ( v == father )  continue; // 防止“回头”向上
        int d = dfs_d(v, u) + w[i]; // 自底向上 先dfs子节点 再计算当前节点
        if ( d >= d1[u] )   d2[u] = d1[u], d1[u] = d, p1[u] = v;
        else if ( d > d2[u] )   d2[u] = d;
    }

    if ( d1[u] == -INF )
        d1[u] = 0; // 叶子节点 向下不经过其他节点 只与父节点相连(被continue掉了)

    return d1[u]; // 返回向下的最大路径值    
}

void dfs_up(int u, int father)
{
    for ( int i = h[u]; ~i; i = ne[i] )
    {
        int v = e[i];
        if ( v == father )  continue;
        if ( p1[u] == v )   up[v] = max( up[u], d2[u] ) + w[i]; //最大路径经过v
        else up[v] = max( up[u], d1[u] ) + w[i];

        dfs_up(v, u); //自上向下 先处理当前节点 再向下递归
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for ( int i = 1; i < n; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    dfs_d(1, -1); //自底向上 求d1[], d2[]

    dfs_up(1, -1); //自上向下 求up[]

    int res = INF;
    for ( int u = 1; u <= n; u ++ )
        res = min( res, max(d1[u], up[u]) );
    cout << res << endl;

    return 0;
}