树形DP求树的直径

思路：

非常套路性的一个东西，记录一下，防止遗忘
设\(f[i]\)表示以\(i\)为根，到其子树的叶节点的最大距离。

考虑如何用子节点更新父节点，
当前点到叶节点的最大距离=max{子节点到叶节点的距离+当前点到子节点的距离}。

设\(u\)为当前节点，\(v\)为\(u\)的子节点，\(dis(u,v)\)是从\(u->v\)这条路径上的距离
得到转移方程：
\[f[u]=max\{f[v]+dis(u,v)\}\]

如何维护以\(u\)为根的子树中的直径呢
以\(u\)为根子树的直径=max{u到叶节点的最大距离+子节点到叶节点的最大距离+\(u\)到叶节点的距离}
然后我们钦定一个节点为根，比如1
得到转移方程：
\[ans=max\{f[u]+f[v]+dis(u,v)\}\]
\(ans\)即为树的直径
需要注意的是，我们要在更新\(f[u]\)之前更新\(ans\)，因为从u经过v到叶节点的路径是最长的路径，这样这条路径会被更新两次

这样做一定会选出u到叶节点最长的两条路径
分类讨论一下

• 更新\(f[u]\)的路径是\(u\)到叶节点的所有路径中最长的，次长的还未被选，那它会和次长（相等）的一同更新最大值
• 更新\(f[u]\)的路径是\(u\)到叶节点的所有路径中次长的，最长的还未被选，那它会和最长的一同更新最大值
• 更新\(f[u]\)路径不是最长也不是次长，那么\(f[u]\)就会被最长或次长的路径更新，然后在转化成上两种情况

代码

void dfs(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (v == fa) continue;
        dfs(v, u);
        ans = max(ans, f[u] + f[v] + e[i].w);
        f[u] = max(f[u], f[v] + e[i].w);
    }
}

练手题

#10155. 「一本通 5.2 例 3」数字转换
边权全为1的树的直径

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m, num, ans;

int head[N], f[N];

struct node {
    int nx, v;
} e[N];

inline int sum(int x) {
    int tmp = 1;
    for (int i = 2; i * i <= x; ++i) if (x % i == 0) {
        tmp += i;
        if (x / i != i) tmp += x / i; 
    }
    return tmp;
}

inline void add(int u, int v) {
    e[++num].nx = head[u], e[num].v = v, head[u] = num;
}

void dfs(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (v == fa) continue;
        dfs(v, u);
        ans = max(ans, f[u] + f[v] + 1);
        f[u] = max(f[u], f[v] + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    memset(head, -1, sizeof head);
    cin >> n;
    for (int i = 1; i <= n; ++i) if (sum(i) < i) 
        add(sum(i), i), add(i, sum(i));
    dfs(1, 0);
    cout << ans;
}

原文链接:https://www.cnblogs.com/lykkk/p/11199812.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有