【树的直径】树上子链

秒速五厘米 2024-03-22 17:39 86阅读 0赞

[F-树上子链\_牛客竞赛动态规划专题班树型dp例题 (nowcoder.com)][F-_dp_ _nowcoder.com]

题意：

![39c6a6eb334648c2bf0532c51512efed.png][]

思路：

树的直径板子题

唯一的区别就是边权变成点权了

Code：

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 1e6 + 5;
    typedef long long LL;
    int n;
    vector<int> mp[N];
    LL dp[N][2], w[N],res[N];
    void dfs1(int now, int fa) {
        dp[now][0]=dp[now][1]=-0x3f3f3f3f3f3f3f3f;
        for (int i = 0; i < mp[now].size(); i++) {
            int ne = mp[now][i];
            if (ne == fa) continue;
            dfs1(ne, now);
            if(dp[now][0]<dp[ne][0]){
                dp[now][1] = dp[now][0];
                dp[now][0] = dp[ne][0];
            }
            else if(dp[now][1]<dp[ne][0]){
                dp[now][1] = dp[ne][0];
            }
        }
        dp[now][0] = max(0ll, dp[now][0]) + w[now];
        dp[now][1] = max(0ll, dp[now][1]) + w[now];
    }
    
    int main() {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> w[i];
        }
        for (int i = 0; i < n - 1; i++) {
            int x, y;
            cin >> x >> y;
            mp[x].push_back(y), mp[y].push_back(x);
        }
        dfs1(1, 0);
        LL ans =-0x3f3f3f3f3f3f3f3f;
        for (int i = 1; i <= n; i++)ans= max(ans,dp[i][0]+dp[i][1]-w[i]);
        cout << ans << endl;
        return 0;
    }

[F-_dp_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/28258/F
[39c6a6eb334648c2bf0532c51512efed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/eefb30597b6c4e41b63944d91ec4bfb9.png

发表评论取消回复

表情：

评论列表（有 0 条评论，86人围观）

还没有评论，来说两句吧...

相关阅读

相关树的直径

树的直径 * 前言 * 源代码 * 参考博客前言路径：一棵树上，任意两个节点之间最多有一条简单路径。我们用 dis(a,b)表示点a和...

- 日理万妓/ 2024年04月17日 18:24/ 0 赞/ 85 阅读

相关【树的直径】树上子链

[F-树上子链\_牛客竞赛动态规划专题班树型dp例题 (nowcoder.com)][F-_dp_ _nowcoder.com] 题意： ![39c6a6eb334648c

秒速五厘米/ 2024年03月22日 17:39/ 0 赞/ 87 阅读

相关 543. 二叉树的直径

打卡!!!每日一题今天给大家带来一道树类型的深度优先遍历题目。对于树类型的题目，无论怎么考无非就是考察前中后序遍历以及层次遍历。当然很多人想当然的认为树的考查只有深

本是古典何须时尚/ 2023年10月11日 18:35/ 0 赞/ 29 阅读

相关 poj 3310 Caterpillar(树的直径)

Caterpillar -------------------- Time Limit: 2000MS Memory Limit: 65536K To

迷南。/ 2023年07月07日 03:35/ 0 赞/ 15 阅读

相关树直径和树重心

主要是留个板子因为我似乎不会证明树直径丛树的任一点开始找一个离该节点最远的点，该点必为树直径的一端点，再从该点出发找最远点即为树直径方法：dfs 时间O(2n)

冷不防/ 2023年06月12日 04:24/ 0 赞/ 19 阅读

相关 543. 二叉树的直径

题目来源 [543. 二叉树的直径][543.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_sha

╰半夏微凉°/ 2022年12月19日 11:39/ 0 赞/ 184 阅读

相关 Leetcode 543. 二叉树的直径(直径 = 左子树高度 + 右子树高度)

题目重述给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。示例 : 给定二叉树

我不是女神ヾ/ 2022年09月02日 11:38/ 0 赞/ 196 阅读

相关树的直径（最远距离）

输入数据 5 5 1 2 2 2 4 3 2 5 1 4 5 4 1 3 5 有5个点5条边 ![Center][] 第一次bfs从1号

拼搏现实的明天。/ 2022年06月15日 04:30/ 0 赞/ 221 阅读

相关树的直径

树的直径树上最长的简单路径即为树的直径。求树的直径的方法就是在树上任选一点u，求距离点u最远的点v，再求距离点v最远的点s，点u到点s的距离即为树的直径。（即两遍D

约定不等于承诺〃/ 2022年05月12日 11:04/ 0 赞/ 201 阅读

相关 SDOI2013 直径（树的直径必经边）

SDOI2013 直径 [题目传送][Link 1] sol: 先求出任一直径同时把直径拎出来，树的非直径部分全部挂在直径上（如下）。 ![a][] 对于直径上的

- 日理万妓/ 2021年11月23日 23:12/ 0 赞/ 322 阅读