单片机
qt
springcloud
devops
代码规范
轨道融合仿真
design_pattern
自述
Pyhton
反码
skill
condition
codeblock
filter
printf
mxnet
编程开发
数据结构和算法
requests库
mes
树形dp
2024/4/11 19:51:18C++ 树形DP入门题详解——树的最大独立集
树的最大独立集
题目描述 对于一棵有N个结点的无根树，选出尽量多的结点，使得任何两个结点均不相邻（称为最大独立集）。
输入 第1行：1个整数N(1 < N < 6000)，表示树的结点个数，树中结点的…
bzoj 1907: 树的路径覆盖
Description Input Output Sample Input 1 7 1 2 2 3 2 4 4 6 5 6 6 7Sample Output 3HINT Source Play with Tree By Amber 自己写了一发贪心WA了。。然后去看题解 f[i]表示i为子树的最小路径覆盖就可以搞定了 或者 http://ydcydcy1.blog.163.com/blog/static/216089040201323…
牛客 Minieye杯第十五届华中科技大学程序设计邀请赛网络赛 I-Tree(二分+树形dp)
题意：一棵树有n个节点，每个节点有一个值，把n个节点分成k个连通的部分，使得k个部分的和的最小值最大。 思路：二分枚举答案，树形dp检查。对于一个节点v，如果他和他的子树的值小于枚举的答案 &…
洛谷P2015 二叉苹果树（树形dp）
题目描述
有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）
这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。
我们用一根树枝两端连接的结点的…
[51nod1299]监狱逃离
Description
给出一个n1个点n条边的树，其中每一个度数为1的点为出口。 现在有一些点有逃犯，你需要在一些没有逃犯的点放置警卫，有警卫的点逃犯无法经过。 求若使所有逃犯均无法到达出口，最少需要多少个警卫。 n<10^5
Solu…
acwing 1077 皇宫看守
题面 题解(树形DP状态机模型) 此题与战略游戏的区别 : 战略游戏是有关边的，每个节点选或者不选，因为要求每条边至少有一个点，所以可以通过父节点来维护出子节点选或者不选，但是这个题是点之间的关系，不能通过父节点来维…
bzoj 1131: [POI2008]Sta
Description 给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大 Input 给出一个数字N,代表有N个点.N<1000000 下面N-1条边. Output 输出你所找到的点,如果具有多个解,请输出编号最小的那个. Sample Input 8 1 4 5 6 4 5 6 7 6 8 2 4 3 4Sample Outpu…
Leetcode.337 打家劫舍 III
题目链接 Leetcode.337 打家劫舍 III mid 题目描述
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有…
【算法】树形DP③ 监控二叉树 ⭐（二叉树染色二叉树灯饰）！
文章目录 前期知识 & 相关链接例题968. 监控二叉树解法1——标记状态贪心解法2——动态规划 相关练习题目P2458 [SDOI2006] 保安站岗⭐（有多个儿子节点）🚹LCP 34. 二叉树染色⭐（每个节点 单独dp[k 1]数组）LCP 64.…
一些二叉树相关面试题
文章目录1. 对折2. 判断是否是平衡二叉树3. 判断是否是搜索二叉树4. 二叉树的直径5. 寻找最大二叉搜索树6. 用递归套路判断是否是完全二叉树7. 派对的最大快乐值1. 对折 这个大家可以自己用纸对折一下，我这里就简单的说一下： 这是我们第一次对折的情况。…
acwing 1072 树的最长路径 （树形DP）
题面 题解 对于没有边权的树的直径的定义是路径上经过的边数最多求解步骤 ：1.任取一点作为起点，找到距离该点最远的一个点u（某一条直径的端点） 2.再找到距离u最远的一点v 3.那么u和v之间的路径就是一条直径 （BFS&#…
刷题记录:牛客NC24953[USACO 2008 Jan G]Cell Phone Network
传送门:牛客
题目描述:
John想让他的所有牛用上手机以便相互交流，他需要建立几座信号塔在N块草地中。已知与信号塔相邻的草地
能收到信号。给你N-1个草地(A，B)的相邻关系，问：最少需要建多少个信号塔能实现所有草地都有信号。
输…
hdu 5723 Abandoned country
Problem DescriptionAn abandoned country has n(n≤100000)villages which are numbered from 1 to n. Since abandoned for a long time, the roads need to be re-built. There are m(m≤1000000)roads to be re-built, the length of each road is wi(wi≤1000000). Guaran…
bzoj 3572: [Hnoi2014]世界树
Description 世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。…
C++ 树形DP经典例题详解——二叉苹果树
引言
这是十分经典的树形DP题，其转移方程很好想到，但有一些坑要注意 题目描述 有一棵苹果树，如果树枝有分叉，一定是分 2 叉（就是说没有只有 1 个儿子的结点）。这棵树共有 N 个结点（叶子点或者树…
Codeforces Round 896 (Div. 1) C. Travel Plan(树形dp+组合数学)
题目
有一棵n(1<n<1e18)个点的树，
点i连着2*i和2*i1两个点，构成一棵完全二叉树
对于每个点i，记其值为a[i]，a[i]可以取[1,m](1<m<1e5)的整数
记i到j的简单路径上的最大值为s[i][j]，
则一棵权值确定的树…
bzoj 2314: 士兵的放置
Description 八中有N个房间和N-1双向通道,任意两个房间均可到达.现在出了一件极BT的事,就是八中开始闹鬼了。老大决定加强安保，现在如果在某个房间中放一个士兵,则这个房间以及所有与这个房间相连的房间都会被控制.现在 老大想知道至少要多少士兵可以控制所有房间.以…
acwing 1220 生命之树 （树形DP）
题面 题解 代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>using namespace std;
typedef long long ll;
const int N 1e5 10, M N * 2;int n;
ll w[N];
ll h[N], e[M], ne[M], idx;
ll …
bzoj 4033: [HAOI2015]T1
Description 有一棵点数为 N 的树，树边有边权。给你一个在 0~ N 之内的正整数 K ，你要在这棵树中选择 K个点，将其染成黑色，并将其他 的N-K个点染成白色 。 将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间…
AcWing 287. 积蓄程度，《算法竞赛进阶指南》
287. 积蓄程度 - AcWing题库
有一个树形的水系，由 N−1 条河道和 N 个交叉点组成。
我们可以把交叉点看作树中的节点，编号为 1∼N，河道则看作树中的无向边。
每条河道都有一个容量，连接 x 与 y 的河道的容量记为 c(x,y)。
河道…
刷题记录:牛客NC202475树上子链
传送门:牛客
题目描述:
给定一棵树 T ，树 T 上每个点都有一个权值。
定义一颗树的子链的大小为：这个子链上所有结点的权值和 。
请在树 T 中找出一条最大的子链并输出。
输入:
5
2 -1 -1 -2 3
1 2
2 3
2 4
2 5
输出:
4一道简单的树形dp的题目,但是有一…
bzoj 2286: [Sdoi2011]消耗战
Description 在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个…
bzoj 3611: [Heoi2014]大工程
Description 国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。 我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。 在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。现在国家有很多个计…
算法竞赛进阶指南---0x54（树形DP）没有上司的舞会
题面 题解 经典的树形DP问题：我们知道，一棵树的父亲和儿子节点不能同时出现，那么我们就可以得到两个状态，选这个父节点和不选这个父节点 f[u][0] : 所有以u为根的子树中选择，并且不选u这个点的方案 f[u][1] : 所有以u为…
codeforces 1529 C.Parsa‘s Humongous Tree
题面 题意 给出一颗n个节点的树，每个节点的值有一个区间范围，问如何选取节点的值才能使这颗树变成完美的树，完美的树满足每条边所连接的两个节点的差值的绝对值之和最大 题解（树形DP） 我们知道，要想使两个节…
【动态规划】【树形dp】【C++算法】968监控二叉树
作者推荐
【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数
本文涉及知识点
动态规划汇总
LeetCode:968监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所…
acwing 1074 二叉苹果树
题面 题解 树形DP分组背包，是有依赖背包那道题的简化版，书上的苹果树就是边的权值，树的分枝就是背包的体积 f[u] [j] : 表示所有以u为根节点的子树中选，选 j 条边的最大价值 以u为根节点的每一颗子树都可以看作是一组背包…
acwing 323 战略游戏
题面 题解（树形DP） 树形DP，可以对比没有上司的舞会这题，没有上司的舞会是要求父子节点不能同时出现，就相当于每条边上最多选一个节点，求最大权值，此题是要求每条边上最少选一个节点，…
acwing 10 有依赖的背包问题
题面 题解 这道题其实更偏向于树形DP，我们设状态方程 f[u] [j] 表示所有以从根节点为 u 的子树中选，体积不超过 j 的最大方案 ，那么最终 f[root][m] 就表示从根节点开始体积不超过m的最大方案 要想算出祖宗节点的的最大方案，我们就…
acwing 1073 树的中心 （树形DP）
题面 题解 我们要枚举每个点到其它点的最远距离，那么就会有两种情况，向上走或者是向下走 假设我们枚举u点，向下走 dfs_down(u) 更新当前节点向下走，叶子节点不需要更新 d1[u] 表示 u点向下的最长路径，d2[u] 表示 u 点…
acwing 1075 数字转换 （树形DP）
题面 题解 首先，对于小于n的每个数，我们可以确定它的约数之和（不包括自己）是固定的，就像4的约数之和一定是3，不可能是其他的，那么我们就可以将2-n的每个数的约数之和求出sum[i]，对于…
仓鼠找sugar II
题目描述
小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a，是任意的）他的基友卧室（b&…
【WC2015模拟2.6】Tree
Description
给出一个n个节点的无根树，每个点有点权。 你要选择一些不相交的路径，如果选择了k条路径，点权和为sum，那么它的价值为sumk1你必须在选择前选择一个数C(0<c<T),将所有点权加上C再对limit取模。 求你能收获的最…
C++解题报告：电话网络——巧用树形DP
电话网络
题目描述
Farmer John决定为他的所有奶牛都配备手机，以此鼓励她们互相交流。 不过，为此FJ必须在奶牛们居住的N(1 < N < 10,000)块草地中选一些建上 无线电通讯塔，来保证任意两块草地间都存在手机信号。所有的N块草地按1..N …
C++解题报告——Rima（字典树+树形DP）
题目描述 Adrian对单词押韵很感兴趣。如果两个单词的最长公共后缀的长度与两个单词中较长那个的长度一样，或者等于较长单词的长度减一，则这两个单词押韵。换句话说，如果A,B的最长公共后缀LCS（A，B）≥max&…
【算法】树形DP ①（树的直径）
文章目录 知识准备例题543. 二叉树的直径124. 二叉树中的最大路径和2246. 相邻字符不同的最长路径 相关题目练习687. 最长同值路径 https://leetcode.cn/problems/longest-univalue-path/solution/shi-pin-che-di-zhang-wo-zhi-jing-dpcong-524j4/1617. 统计子树中城市之间最大…
赛后补题:2022 CCPC Guangzhou I. Infection 树形背包dp+概率贡献
传送门:牛客
题目描述:
题目较长,此处暂略
输入:
5
2 1
5 2
3 2
4 3
2 1 5
3 1 2
2 1 1
2 1 1
3 1 2
输出:
208333335
166666668
166666668
950000007
508333337一道树形dp的题目,官方题解说这是一道简单题?然而我感觉这道题至少比同场次比赛的那道图论题要难,赛时对于这道题…
树形DP问题C++详解
树
在学习树形dp之前我们先了解一下什么是树。树简单来说就是连通的无环图。
树的存储
保存边信息的树的模板如下：
a表示加边的起点，b表示加边的终点，c表示加边的权值
const int N 1e4 10;
int end[N], worth[N];
int next[N], head[N…
C++深度优先搜索的应用：在树上执行操作以后得到的最大分数
涉及知识点
深度优先搜索(DFS)
题目
有一棵 n 个节点的无向树，节点编号为 0 到 n - 1 ，根节点编号为 0 。给你一个长度为 n - 1 的二维整数数组 edges 表示这棵树，其中 edges[i] [ai, bi] 表示树中节点 ai 和 bi 有一条边。 同时给你一个…
美团笔试 最优二叉树II（树形DP）
2021年04月21日 周三 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】 本文目录1. 题目简介2. 树形DP参考文献1. 题目简介
最优二叉树II
2. 树形DP
图源：shanxiansen310
#include<bits/stdc.h>
using namespace std;
// 最大节点个…
23.8.8 杭电暑期多校7部分题解
1008 - H.HEX-A-GONE Trails
题目大意
有两个玩家和一棵树，初始状态玩家一和玩家二分别在两个点 x , y x,\space y x, y，每次操作可以走一个与当前点有连边并且双方都没走到过的点，问最后是谁赢
解题思路
因为不能走走过的点，…
点分治维护dp+连通块上新型dp思路+乘积方面进行根号dp：0922T4
首先连通块，所以点分治肯定是
Trick1 钦定选根的连通块dp
对于钦定选根的连通块dp，有一种常见思路
先对原树求其dfn序，按dfn序倒序求解
具体的，对于当前点 i i i（注意这里都是指dfn序），我们…
2023 CCPC 华为云计算挑战赛 hdu7401 流量监控(树形dp)
题目
流量监控 - HDU 7401 - Virtual Judge
简单来说，T(T<20)组样例，sumn不超过2e4
每次给定一棵n(n<2000)个点的树，两问：
①将n个点恰拆成n/2个pair(u,v)，要求一个点是另一个点的祖先，求方案数 …
树形DP——没有上司的舞会
原题链接
分析
状态表示： f[u][0]：表示以u为根结点但是不选择u快乐值的最大值 f[u][1]：表示以u为根结点且选择u的快乐值的最大值
状态转移： f[u][0]：对于这种情况我们可以选择u结点的孩子也可以不选择u结点的孩子&a…
gym 101667 A -Broadcast Stations【树形dp】
A 树形dp
题目大意：
一棵5e3的树，可以选择一些点，放上基站，如果u上的基站价值为d，那么距离u小于等于d的点都会被覆盖，问使得整棵树被覆盖需要的最小价值。
题目分析
设 f[u][i]f[u][i]f[u][i] 表示从 u…
Leetcode—2646.最小化旅行的价格总和【困难】
2023每日刷题（五十三）
Leetcode—2646.最小化旅行的价格总和 算法思想
看灵神的
实现代码
class Solution {
public:int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector&l…
Leetcode—337.打家劫舍III【中等】
2023每日刷题（五十二）
Leetcode—337.打家劫舍III 算法思想 实现代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(null…
用树形dp+状压维护树上操作的计数问题：0902T3
发现操作数 k ≤ 6 k\le6 k≤6，可以考虑对操作进行状压。
然后找找性质，发现要么删掉一棵子树，要么进去该子树。可以视为每种操作有两种情况。
然后分讨一下当前该如何转移。
树形dp的顺序：
合并子树考虑当前往上的边的方向 …
HDU1520——Anniversary party（树形DP）
题意：有n个人，他们之间有上司和下属关系，每个人有自己的价值，现在要选一部分人使其满足上司和下属不同时被选到的情况下价值总和最大。更直接的讲就是，在一棵树中选价值总和尽量多的节点但是不能同时选到一个节点和它的…
23.3.8打卡 AcWing 1072. 树的最长路径 树形dp
AcWing 1072. 树的最长路径
题目链接: https://www.acwing.com/problem/content/1074/
听y总的课听睡着了, 直接看的题解琢磨了下, 感觉挺简单的
题意
给你一棵树, 找到这棵树的最长路径
题解
先说屁话, 感觉能用最长路写, 最短路改改就好了 当然这是个树形dp的模板题这里…
POJ 2342 | HDU 1520 Anniversary party 树形DP（入门题）
传送门：POJ 2342题目大意：
有若干人参加一个聚会，如果两个人之间有直接的上下属关系，则只能去一个。每个人都有个高兴值，问高兴值之和最大是多少？思路：
之前一直觉得树形DP比较难，现…
【NOIP2016提高A组五校联考4】label
Description
给出一个n个节点的树，每个节点可以填[1,m]中的任意一个数。 相邻节点的数的绝对值必须>k 求方案数 n,k<100,m<10^9
Solution
首先我们考虑如何解决一条链上的 如果不考虑m的范围，我们有一个显然的dp 太显然不写了。。。 观…
石油大 Contest1777 - 2019年第二阶段我要变强个人训练赛第九场 I 热狗树（树形dp）
题目描述 “我是番茄酱！” “我是黄芥末酱！” “合在一起就是——美式热狗上加的，那个！“ 热狗树上的每个节点都涂有番茄酱或者黄芥末酱中的一种，这样热狗树就变得美味了~LiMn2O4构造了一颗热狗树，他想知道…