原理本题判断一个二叉树是否为平衡二叉树，核心思路是基于平衡二叉树的定义，即任意节点的左右子树的高度差的绝对值不超过1。通过递归地计算每个节点为根的子树的高度，在计算过程中判断是否满足高度差条件，如果发现某个节点的左右子树高度差超过1，则整棵树不是平衡二叉树，标记为特

题目链接树形DP简要题意\(n\)个点的树，其中\(k\)个点染黑色，\(n-k\)个点染白色，求黑点两两距离之和加白点两两之和的最大值。思路我们首先考虑如果\(k=0\)时，答案应该怎么算，此时显然是\(\sum_{i=1}^n\sum_{j=i+1}^ndis(i,j)\)。然后我们考虑如何在\(O(n)\)的时间复杂度

最小斯坦纳树定义摘自百度百科的定义：斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。实现例题：P6192【模板】最小斯坦纳树-

树状数组作用：动态地维护前缀和查询Timecomplexity修改一个数:$$o(lgn)$$查询一段区间和：$$o(lgn)$$实现过程1lowbit返回一个数的二进制下末尾第一个1和后面的0构成的数如11011000100返回100=4intlowbit(intx){ returnx&(-x);}2建立树状数组定义$$t[x]$$保存

要找到无序整数数组中最小值和最大值之间缺失的数字，并保证最小的时间复杂度，可以使用以下方法：1.使用集合(Set)这是最简洁且时间复杂度较低的方法，时间复杂度为O(n)，空间复杂度也是O(n)。functionfindMissingNumbers(arr){if(!arr||arr.length<2){return[];/

首先不难发现，确定了根以后答案是固定的。设\(sz_i\)表示以1为根的树中，以1为根的子树大小；\(f_i\)表示以1为根的树中，以\(i\)为根的子树得到的最大权值，可以得到转移\[f_u=sz_u+\sum_{v\inson_u}f_v\]然后设\(g_v\)表示先选\(v\)的最大权值，\(v\)的父亲为\(

 强连通分量-OIWiki(oi-wiki.org)   从以u为根的子树中的任意点出发。单次到达（从这个点指向某个点，有一条边）的这些点中的dfn的最小值 以v为根的子树，包含在以u为根的子树中，low[v]所用的子节点，一定也可以被low[u]，这个点一定在以u为根的子树里，所以用low[v]  从

在树上运行的dp叫做树形dp。题单。树形dp入门问题例1.1：没有上司的舞会我们发现，对于一个节点，要么选或不选，且题目中要求求出权值最大的方案，不妨分别设\(dp_{i,0},dp_{i,1}\)为在以\(i\)为根的子树中，第\(i\)个点选或不选情况下的最大权值。那么可以得到\[dp_{i,0}=

\(\text{LuoguP1552[APIO2012]派遣}\)前置芝士：可并堆（左偏树）或斜堆或启发式合并。本题题意概括为：给定一颗以\(1\)为根的树，每个点有权值\(L_i\)，花费\(C_i\)，可以选择一个以某个结点为根的子树，并从其中选出一个点集\(T\)满足\(\sum_{i\inT}C_i\leqM\)，那么此次的价

一道很好的树形dp！！！！！树上染色。错误思路定义\(dp[u][i]\)表示以\(u\)为根的子树中，把\(i\)个点染成黑色的最大收益。但这样写，就在转移的时候必须枚举每一个点，复杂度过大，而且还不好写，是十分错误的写法。正确思路一般看到有关树上“路径”的题，就要把路径拆成一个个独立的

题目传送门前置知识二分答案|树形DP解法答案显然具有单调性，考虑二分答案。设当前二分出的答案为\(mid\)，则等价于覆盖距离为\(mid\)的情况下进行选点。做法同luoguP3942将军令，考虑进行贪心，对于深度最深的叶节点将选择的点放在边界时，即取\(mid\)级祖先时，覆盖的范

状态设计基本上每一种dp都有一种标准的dp定义方式，树形dp也是如此：定义\(f[u]\)表示以\(u\)为根节点的子树里最优的决策。从分析子树入手，转移便是找到某一子树中，根节点与各子树、边权间的递推关系。最优解常常是关于根节点的函数。它的子结构是一颗子树。实现方式

背景汗流浃背了。分析容易想到一个显然的思路：以任意节点为根，开始遍历。如果一个节点的子树里面有黑点，那么它必须保留，否则如果它是白点，则可以删去。但这个方法很容易举出反例：在这颗树中，如果以最上面的白点为根，那么手推发现算法显然错误。尝试进行修改，容易发现，对于类似的情况

题目大意每次在每个联通块中选一个点\(u\)，删除这个点使得联通块分成若干个联通块，再从联通块中选点\(v\)，在新树上连接\(u,v\)，求新树叶节点的最大个数。分析易转化为求原树的最大独立集，设\(f_{u,0/1}\)为以1为根时不选/选\(u\)的最大独立集。显然有:\[dp_{u,0}=\sum\li

多重背包&树上背包多重背包有\(n\)种物品，每种物品有\(s_i\)个，价值为\(v_i\)，体积为\(w_i\)，背包容量为\(V\)，问最大价值二进制拆分把\(s\)进行二进制拆分，然后就是01背包的过程，\(O(nV\logV)\)可以用bitset优化单调队列对于每个物品，先枚举\(k=0\simw_i-1\)，然后枚

题目链接：最大子树和思路    由于可以无限剪枝，所以假设以节点1为根，并删去所有美丽质数小于0的子树，又考虑到可能会出现根节点为负数，导致可能会只留下子树而把节点1为根节点的其他部分扔掉，所以需要dp数组记录，dp[i]为以节点i为根节点能得到的最大的美丽指数，贪心将节点i的子

题意:给定k颗有n个点的树对于每个点对(i,j)，求出其在每棵树上的路径经过的点（含端点）的并集大小。做法:一个比较简单的想法是搞出每个(i,j)在第k颗树上的点的集合，然后所有树并一下，这个再用bitset优化一下，然后有人就过了，而我这位大常数选手就没过。首先容斥为求不经过点的交。考

oj:https://gxyzoj.com/d/hzoj/p/3575因为自己的脑残原因，调了8个小时啊！！！切入正题Part1假定1为根，可以发现，如果u的两棵子树同构，则他们遍历的顺序不影响答案所以，就可以将子树按哈希值分类，这道题就变成了一个可重复组合问题，设\(f_i\)表示以1为根时i的方案数，\(a_i\)表示某一种哈

问题描述给定一棵包含n个结点的完全m又，结点按从根到叶、从左到右的顺序依次编号。例如下图是一个拥有11个结点的完全3叉树。CR你需要求出第k个结点对应的子树拥有的结点数量输入格式输入包含多组询问。输入的第一行包含一个整数T，表示询问次数接下来T行，每行包含三个整

【问题描述】首先输入扩展二叉树的前序序列，构建二叉树，然后输入希望删除的节点，输出删除后二叉树的前序和中序遍历序列。【输入形式】输入扩展二叉树的前序序列。【输出形式】分两行分别输出删除后二叉树的前序和中序遍历序列。【样例输入】ab##cd##e##c【样例输出】

学习笔记索引省流：被吊打了自己开的一个坑，死也要填完它。希望我随手写下的笔记对您的学习有所帮助（也不太可能）。更改日志2024/01/08：开坑，写了树的直径和换根DP，写不动了（（（2024/01/08晚上：更新了最小点覆盖和最大独立集，看来精神还可以，顶着明天做手术的风险2024/01/09：修改错误+增补

树形dp，又称树状dp，即在树上进行的dp，在设计动态规划算法时，一般就以节点从深到浅（子树从小到大）的顺序作为dp的“阶段”，dp的状态表示中，第一维通常是节点编号（代表以该节点为根的子树）。大多数时候，我们采用递归的方式实现树形动态规划。对于每个节点x，先递归在他的每个子节点上进行dp，在回溯

简单的树上dp其实已经在普及组涉及过：自上而下和自下而上传递的性质。现在我们需要研究更复杂的树上dp，比如换根dp等等。【树上dp】最大子树和给出一棵带点权的树，求这棵树中的最大权连通块。因为是无根树，我们人为规定1号结点为根。\(dp[i]\)表示以\(i\)为根的子树

原题链接题解很简单想到暴力，但是\(O(n^2)\)显然不行所以要减少计算量，如何利用已经计算过的值而不是重新算一遍呢？这道题最好看成有中心点的网状图，而不是树状图随便取一个点\(A\)作为根节点，很容易计算其答案，如何计算以其他点为根节点的答案呢？对于以根节点的邻边节点\(B\)

很容易想出一个状态，设\(f[i][j][0/1]\)表示以\(i\)为根节点，安装\(j\)个监听器，根节点是否安装了监听器的总方案数然后你去推，就会发现我们还需要知道根节点是否被监听这一个信息（最开始\(0/1\)那一维设成根节点是否被监听也是会发现需要知道根节点是否安装了监听器）所以我们设成\(f[