最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

给定一棵树，树中包含 $n$ 个 节点 和 $n−1$ 条 无向边，每条边都有一个权值 $w_{edge_i}$

请在树中找到一个点，使得该点到树中其他结点的 最远距离 最近

分析

这个问题是 树形DP 中的一类 经典模型，常被称作 换根DP

同样，先来想一下如何暴力求解该问题：先 枚举 目标节点，然后求解该节点到其他节点的 最远距离

时间复杂度为 $O(n^2)$，对于本题的 数据规模，十分极限，经测试只能过 $6/10$

考虑如何优化求解该问题的方法

思考一下：在确定树的 拓扑结构 后单独求一个节点的 最远距离 时，会在该树上去比较哪些 路径 呢？

1. 从当前节点往下，直到子树中某个节点的最长路径
2. 从当前节点往上走到其父节点，再从其父节点出发且不回到该节点的最长路径

此处就要引入 换根DP 的思想了

换根DP 一般分为三个步骤：

1. 指定任意一个根节点
2. 一次dfs遍历，统计出当前子树内的节点对当前节点的贡献
3. 一次dfs遍历，统计出当前节点的父节点对当前节点的贡献，然后合并统计答案

那么我们就要先 dfs 一遍，预处理出当前子树对于根的最大贡献（距离）和 次大贡献（距离）

处理 次大贡献（距离） 的原因是：

如果 当前节点 是其 父节点子树 的 最大路径 上的点，则 父节点子树 的 最大贡献 不能算作对该节点的贡献

因为我们的路径是 简单路径，不能 走回头路

然后我们再 dfs 一遍，求解出每个节点的父节点对他的贡献（即每个节点往上能到的最远路径

两者比较，取一个 max 即可

时间复杂度 为 $T(2n) = O(n)$

闫氏DP分析法

状态表示—集合$f_{1/2,i}$: 对于树中 $i$ 号节点，其子节点的贡献为$f_{1,i}$，父节点的贡献为 $f_{2,i}$
状态表示—属性$f_{1/2,i}$: 贡献值最大
状态计算—$f_{1/2,i}$
$$ \begin{cases} f_{1,i} = \max\{f_{1,i_{c} }\}\\\ f_{2,i} = \max\{f_{1,i_{p}}~~, f_{2,i_{p}}\} \quad(son_{i_p}\ne i) \end{cases} $$

Code

时间复杂度： $O(n)$

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

using namespace std;

const int N = 10010, M = N << 1, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], w[M], ne[M], idx;
int d1[N], d2[N], up[N];
int s1[N], s2[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs1(int u, int father)
{
    // d1[u] = d2[u] = -INF;  //这题所有边权都是正的，可以不用初始化为负无穷
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u);
        if (d1[j] + w[i] >= d1[u])
        {
            d2[u] = d1[u], s2[u] = s1[u];
            d1[u] = d1[j] + w[i], s1[u] = j;
        }
        else if (d1[j] + w[i] > d2[u])
        {
            d2[u] = d1[j] + w[i], s2[u] = j;
        }
    }
    // if (d1[u] == -INF) d1[u] = d2[u] = 0; //特判叶子结点
}
void dfs2(int u, int father)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        if (s1[u] == j) up[j] = w[i] + max(up[u], d2[u]);   //son_u  = j，则用次大更新
        else up[j] = w[i] + max(up[u], d1[u]);              //son_u != j，则用最大更新
        dfs2(j, u);
    }
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for (int i = 1; i < n; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    dfs1(1, -1);
    dfs2(1, -1);

    int res = INF;
    for (int i = 1; i <= n; i ++ ) res = min(res, max(d1[i], up[i]));
    printf("%d\n", res);

    return 0;
}

Code（直接暴力换根）

时间复杂度： $O(n^2)$ 通过数据 $60\%$

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

using namespace std;

const int N = 10010, M = N << 1, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], w[M], ne[M], idx;
int d1[N], d2[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs(int u, int father)
{
    d1[u] = d2[u] = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        int dist = dfs(j, u) + w[i];
        if (dist >= d1[u]) d2[u] = d1[u], d1[u] = dist;
        else if (dist > d2[u]) d2[u] = dist;
    }
    return d1[u];
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for (int i = 1; i < n; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    int res = INF;
    for (int i = 1; i <= n; i ++ ) res = min(res, dfs(i, -1));
    printf("%d\n", res);
    return 0;
}