树的直径树的直径有两种求法，一种是两次dfs，一种是树形dp 两次dfs从任意一点跑dfs找到最远点，这个点是直径的一段，再从这个点dfs到最远端，也就是直径的另外一端 这个oiwiki上讲的很细，但我更喜欢他的证明 证明使用反证法。记出发节点为 。设真实的直径是 ，而从 进行的第一次 DFS 到达的距离其最远的节点 不为 或 。共分三种情况...

2025 7 7 学习报告树链剖分是指一种对树进行划分的算法，它先通过轻重边剖分（Heavy-Light Decomposition）将树分为多条链，保证每个点属于且只属于其中一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。 定义size[i] 以结点i为根的子树中结点的个数；son[i] 结点i的重儿子；dep...

同余最短路这是一个很有意思的算法，用于解决给定 n 个整数，求这 n 个整数能拼凑出多少的其他整数（n 个整数可以重复取）这一类问题，目的用于优化空间复杂度 例题有 种硬币，面额 求能凑出 中，有多少价钱可被凑出。 暴力做法考虑完全背包，但是 ，不可做 正解我们用 来作为 这样，我们可以用 来表示 的任意一数于是，我们对 的所有...