动态规划-树形DP

这篇具有很好参考价值的文章主要介绍了动态规划-树形DP。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

树的重心

题目

链接:https://www.acwing.com/problem/content/848/

给定一颗树,树中包含 n n n 个结点(编号 1 ∼ n 1 \sim n 1n)和 n − 1 n-1 n1 条无向边。

请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。

重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。

输入格式

第一行包含整数 n n n,表示树的结点数。

接下来 n − 1 n-1 n1 行,每行包含两个整数 a a a b b b,表示点 a a a 和点 b b b 之间存在一条边。

输出格式

输出一个整数 m m m,表示将重心删除后,剩余各个连通块中点数的最大值。

数据范围

1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1n105

输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例:
4

思路

任取一点u,如果以u为重心,则分为如下两类:

  • u的子树
  • u上面的部分

需要算出这两者的节点数,取最大值。具体细节见代码

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 1e5 + 10;
vector<int> e[N];
int n;
int sz[N]; //记录u的最大子树的节点数
int ans = 1e9;

void dfs(int u, int fa) { //u:当前点,fa:父节点
    sz[u] = 1;
    int mx = 0; //记录u上面的点和子节点连通块的最大值
    for (auto j: e[u]) {
        if (j == fa) continue; //防止向上搜索
        dfs(j, u);
        sz[u] += sz[j];
        mx = max(mx, sz[j]);
    }
    mx = max(mx, n - sz[u]);
    ans = min(ans, mx);
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

树的最长直径

题目

链接:https://www.acwing.com/problem/content/1074/

给定一棵树,树中包含 $ n $ 个结点(编号$ 1   ~   n $)和 $ n-1 $ 条无向边,每条边都有一个权值。

现在请你找到树中的一条最长路径。

换句话说,要找到一条路径,使得使得路径两端的点的距离最远。

注意:路径中可以只包含一个点。

输入格式

第一行包含整数 $ n $。

接下来 $ n-1 $ 行,每行包含三个整数 $ a_i,b_i,c_i $,表示点 $ a_i $ 和 $ b_i $ 之间存在一条权值为 $ c_i $ 的边。

输出格式

输出一个整数,表示树的最长路径的长度。

数据范围

$ 1 \le n \le 10000 $,
$ 1 \le a_i,b_i \le n $,
$ -10^5 \le c_i \le 10^5 $

输入样例:
6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
输出样例:
22

思路

任取一点u,从u点向下搜索,返回时收集边的权值,记录两条路径:

  • d1:记录从u点往下走的最长路径的长度
  • d2:记录从u点往下走的次长路径的长度

更新答案:ans=max(ans,d1+d2)

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 10010;
int n, ans;
typedef struct edge {
    int v, w;
} edge;

vector<edge> e[N];

int dfs(int u, int fa) {
    int d1 = 0, d2 = 0;//最长和次长
    for (auto j: e[u]) {
        auto [v, w] = j;
        if (v == fa) continue;
        int d = dfs(v, u) + w;
        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }
    ans= max(ans,d1+d2);
    return d1;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        e[a].push_back({b, c});
        e[b].push_back({a, c});
    }

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

树的中心

题目

链接:https://www.acwing.com/problem/content/1075/

给定一棵树,树中包含 $ n $ 个结点(编号$ 1   ~   n $)和 $ n-1 $ 条无向边,每条边都有一个权值。

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

输入格式

第一行包含整数 $ n $。

接下来 $ n-1 $ 行,每行包含三个整数 $ a_i,b_i,c_i $,表示点 $ a_i $ 和 $ b_i $ 之间存在一条权值为 $ c_i $ 的边。

输出格式

输出一个整数,表示所求点到树中其他结点的最远距离。

数据范围

$ 1 \le n \le 10000 $,
$ 1 \le a_i,b_i \le n $,
$ 1 \le c_i \le 10^5 $

输入样例:
5 
2 1 1 
3 2 1 
4 3 1 
5 1 1
输出样例:
2

思路

开一个数组p:p[u]记录从u点向下走点最长路径是从哪个点下去的

动态规划-树形DP

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 100010;
int ans = 2e9;
int n;
typedef struct edge {
    int v, w;
} edge;

vector<edge> e[N];
int d1[N], d2[N], up[N], p[N];

void dfs1(int x, int fa) {
    for (auto item: e[x]) {
        int y = item.v, w = item.w;
        if (y == fa) continue;
        dfs1(y, x);
        if (d1[y] + w > d1[x]) {
            d2[x] = d1[x], d1[x] = d1[y] + w, p[x] = y;
        } else if (d1[y] + w > d2[x]) d2[x] = d1[y] + w;
    }
}

void dfs2(int x, int fa) {
    for (auto item: e[x]) {
        int y = item.v, w = item.w;
        if (y == fa)continue;
        else if (y == p[x]) up[y] = max(up[x], d2[x]) + w;
        else up[y] = max(up[x], d1[x]) + w;
        dfs2(y, x);
    }
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        e[a].push_back({b, c});
        e[b].push_back({a, c});
    }
    dfs1(1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; i++) {
        ans = min(ans, max(d1[i], up[i]));
    }
    cout<<ans<<endl;


    return 0;
}

数字转换

题目

链接:https://www.acwing.com/problem/content/1077/

如果一个数 $ x $ 的约数之和 $ y $(不包括他本身)比他本身小,那么 $ x $ 可以变成 $ y , , y $ 也可以变成 $ x $。

例如,$ 4 $ 可以变为 $ 3 , , 1 $ 可以变为 $ 7 $。

限定所有数字变换在不超过 $ n $ 的正整数范围内进行,求不断进行数字变换且不出现重复数字的最多变换步数。

输入格式

输入一个正整数 $ n $。

输出格式

输出不断进行数字变换且不出现重复数字的最多变换步数。

数据范围

$ 1 \le n \le 50000 $

输入样例:
7
输出样例:
3
样例解释

一种方案为:$ 4 \to 3 \to 1 \to 7 $。

思路

因为每个数x的约数之和y是固定的,但是一个约数之和y有可能是很多数x产生的,因此我们可以从yx连边,这样就可以构成一棵树了,反之就不会构成树

这样建图的方式会构造出很多的树

如何求每个数的约数:

可以使用试除法求约数,这样的时间复杂度为 O ( n n ) O(n\sqrt{n}) O(nn )本题应该可以过

也可以利用晒法的思想,对于一个数x,去枚举它的倍数(2倍,3倍…),把这些倍数的数都加上数x,这样做的时间复杂度为调和级数 l n n + C lnn+C lnn+C,因此时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)

构造完树之后,求最多的变换次数即变成了求树的最长直径,可以参考代码模版。文章来源地址https://www.toymoban.com/news/detail-472671.html

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 5e4 + 10;

vector<int> e[N];
int res = 0;
int d1[N], d2[N];
bool st[N];
int n;
int sum[N];

void dfs(int x, int fa) {
    for (auto y: e[x]) {
        if (y == fa) continue;
        dfs(y, x);
        if (d1[y] + 1 > d1[x]) d2[x] = d1[x], d1[x] = d1[y] + 1;
        else if (d1[y] + 1 > d2[x]) d2[x] = d1[y] + 1;
    }
    res = max(res, d1[x] + d2[x]);
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n;
    //统计每个数的约数之和
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= n / i; j++) {
            sum[i * j] += i;
        }
    }
    //建图
    for (int i = 2; i <= n; i++) {
        if (sum[i] < i) {
            e[sum[i]].push_back(i);
            st[i] = true;
        }
    }
    for (int i = 1; i <= n; i++)
        if (!st[i]) dfs(i, i);
    cout << res << endl;
    return 0;
}

到了这里,关于动态规划-树形DP的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划day09(打家劫舍,树形dp)

    目录 198.打家劫舍 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中遇到的困难 213.打家劫舍II 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中遇到的困难 337.打家劫舍 III(树形dp) 看到题目的第一想法 看到代码随想录之后的想法 自己实现过程中

    2024年01月23日
    浏览(91)
  • 算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2024年02月01日
    浏览(41)
  • acwing算法基础之动态规划--数位统计DP、状态压缩DP、树形DP和记忆化搜索

    暂无。。。 暂无。。。 题目1 :求a~b中数字0、数字1、…、数字9出现的次数。 思路:先计算1~a中每位数字出现的次数,然后计算1~b-1中每位数字出现的次数,两个相减即是最终答案。 那么,如何计算1~a中每位数字出现的次数呢? 首先,将a的每一位存入向量num中,例如a=123

    2024年02月04日
    浏览(49)
  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(42)
  • 11.动态规划:树形DP问题、树上最大独立集、树上最小支配集、换根DP、树上倍增(LCA)【灵神基础精讲】

    回溯和树形DP的区别(什么时候需要return结果?):对于回溯,通常是在「递」的过程中增量地构建答案,并在失败时能够回退,例如八皇后。对于递归,是把原问题分解为若干个相似的子问题,通常会在「归」的过程中有一些计算。如果一个递归能考虑用记忆化来优化,就

    2024年02月04日
    浏览(40)
  • 【LeetCode动态规划#11】打家劫舍系列题(涉及环结构和树形DP的讨论)

    力扣题目链接(opens new window) 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非

    2023年04月21日
    浏览(36)
  • 【十七】【动态规划】DP41 【模板】01背包、416. 分割等和子集、494. 目标和,三道题目深度解析

    动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重

    2024年02月03日
    浏览(43)
  • 动态规划(DP)入门——线性DP

    在了解线性DP之前,我们首先要知道什么是动态规划,即为将一种复杂问题,分解成很多重叠的子问题,并通过子问题的解得到整个问题的解的算法。听起来比较抽象,动态规划简单来说就是确定问题的状态,通常题目都会提示,一般为“到第i个为止,xx为j(xx为k)的方案数/最

    2024年02月19日
    浏览(47)
  • 动态规划dp-过河卒

    A点有一个过河卒,需要走到目标B点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如上图的 C 点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图℃ 点上的马可以控制9个点(图中的P1,P2...P8和C)。卒不能通过对方马的控制点

    2024年04月11日
    浏览(39)
  • 算法——动态规划(DP)——递推

    动态规划常用于解决优化问题。 动态规划通常以自底向上或自顶向下的方式进行求解。 自底向上的动态规划从最简单的子问题开始,逐步解决更复杂的问题,直到达到原始问题。 自顶向下的动态规划则从原始问题出发,分解成子问题,并逐步求解这些子问题。 动态规划算法

    2024年01月20日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包