THE NOTEBOOK
按难度探索 →全部文章
ACM / 树上算法基础
树的重心ACM / 树上算法基础
完全二叉树的公共父结点1.有点后序遍历的思想，就是先把左子树，右子树的结果算出来，然后合并到根节点。 2.合并时四种情况分类讨论. 3.对于遇到要找的点就可以直接返回，不管另一个点在这个点下面还是在别的子树上，都是正确的
ACM / 树上算法专题
虚树模板： 题意：给定一颗树，q次查询，每次查询k个点，每个边有砍断的代价，求最少砍断多少条边使得这k个点都无法到达1号根节点。保证 Sol：对于这样的询问点集总和有保证的，可以考虑虚树。对于k个关键点，虚数最多2k个点，这样总和还是级别的，复…
ACM / 树上算法基础
为什么树的dfs不需要vis数组，只需要维护父节点就可以？无向图无环的，无环的图总是可以展成树的形式。 然后考虑无向图，顶多有回边指向父节点。不可能有回边指向祖先。更不可能有横向边，因为无环啊。所以只需要考虑指向父节点的回边就可以无需使用Vis。
ACM / 字符串基础
字符串哈希ACM / 字符串基础
trie字典树如果求最小异或对，除了字典树外，有一个结论：n个数求最小异或对，排序后，一定是相邻的一对数。因为一个数和次小数，次次小数来异或，后者高位不同的多。 最小异或对必定是n个点排完序后，相邻两个点产生的异或值中的一个 给出证明 https://b…
ACM / 数学基础
5156ACM / 树上算法提高
树上背包1.https://www.luogu.com.cn/problem/P1122给定一棵树，每个点有点权，可能为负，求最大权值联通块。 Sol：我们考虑以1为根。树定向后对于任意一个连通块来说，他的形态也一定是一棵树，我们考虑在它的根上会计…