树形dp 树形动态规划（Tree DP）就是在树形结构上进行的动态规划。 在树形结构中，每个节点通常连接着若干子节点，但只有一个父节点。树形DP利用了树的这种结构特点，在动态规划的过程中以节点为单位进行递推，从叶子节点开始，向上逐层计算直至根节点。 由于树形结构天然地包含了递归特性，因此递归式的DP是一种常用的方法。 换根dp 也叫二次扫描法 通常是先计算以0节点为root出发的结果，记为res[0]，而以其它节点为root出发的结果可以通过与res[0]的差值相加得到 834. 树中距离之和 2581. 统计可能的树根数目(2228) 其它树形dp 2920. 收集所有金币可获得的最大积分(2351)

最近公共祖先 描述 问题就是寻找树上两个节点的最近公共祖先节点 边权重均等查询 此题难度超过2500 现有一棵由 n 个节点组成的无向树，节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi, wi] 表示树中存在一条位于节点 ui 和节点 vi 之间、权重为 wi 的边。 另给你一个长度为 m 的二维整数数组 queries ，其中 queries[i] = [ai, bi] 。对于每条查询，请你找出使从 ai 到 bi 路径上每条边的权重相等所需的 最小操作次数 。在一次操作中，你可以选择树上的任意一条边，并将其权重更改为任意值。 注意： 查询之间 相互独立 的，这意味着每条新的查询时，树都会回到 初始状态 。 从 ai 到 bi的路径是一个由 不同 节点组成的序列，从节点 ai 开始，到节点 bi 结束，且序列中相邻的两个节点在树中共享一条边。 返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 条查询的答案。 示例 1： 1234567输 ...

树状数组 概念 树状数组（Fenwick Tree）是一种数组实现的树状结构，常用于解决前缀和问题。它能够在O(log n)的时间内进行单点更新与区间查询操作，特别适用于在动态变化的数组中进行频繁的前缀和查询和更新。 通常需要对输入数据进行离散化，因为数据通常是不连续，而数组要求索引连续 操作 单点修改：更改数组中一个元素的值 区间查询：查询一个区间内所有元素的和 范围：[1, n]; 例如：7（111） 单点修改：111 -> 1000 区间查询：111 -> 110 -> 100 前缀和模板 注意不能add(0, val)，无法跳出循环，因为lowbit(0) = 0 1234567891011121314151617181920212223242526class FenwickTree { int[] tr; // [1, n] public FenwickTree(int[] nums) { // [0, n-1] this.tr = new int[nums.length+1]; f ...

基环树 (pseudotree) 在基环树中，除了环上的节点之外，其他节点都只属于一条路径，从根节点到其他节点都是唯一的。 每一个内向基环树（连通块）都由一个基环和其余指向基环的树枝组成 相关题解 2127. 参加会议的最多员工数

字典树 概念 字典树，也称为前缀树（Trie树），是一种用于存储和管理一组字符串数据的树状数据结构。字典树的主要特点是能够有效地支持字符串的插入和查找操作，以及高效地完成具有相同前缀的字符串的检索。 字典树是一种多叉树结构，每个节点代表一个字符，根节点通常为空。从根节点到某个节点的路径上的字符连接起来即构成一个字符串。 模板 添加和搜索操作的模板 12345678910111213141516171819202122232425262728class Trie { class TrieNode { boolean end; // int cnt; // 维护节点数量 TrieNode[] children = new TrieNode[26]; } TrieNode root = new TrieNode(); void insert(String word) { TrieNode cur = root; for (char c : word.toCh ...

线段树 概念 线段树是一种用于解决区间更新和区间查询问题的高效数据结构 这里我把区间更新分成两种（upd函数） 区间添加更新，给这个区间的子数组都添加上某个值 区间覆盖更新，把这个区间的子数组都赋值为某个值 而区间查询也大概分为两种（query函数） 区间和查询，求这个区间的数组的元素值之和 区间最大值查询，求这个区间的数组的元素值的最大值 数组无lazy线段树 模板：区间添加更新，区间和查询 12345678910111213141516171819202122232425262728293031323334353637383940414243444546class SegmentTree { int[] nums; int len; int[] tree; public SegmentTree(int[] nums) { this.nums = nums; this.len = nums.length; tree = new int[4 * len]; build(1 ...