挺好一题，能学到许多东西。 首先看到题面所求是由对每一条边考虑产生的点的信息和，如果顺着题目的思路思考那肯定是枚举边，用边的限制考虑边的贡献，在仔细考虑一下重心相关的限制，基本就能想到倍增，预处理等方法去动态地对每条边去计算对应的重心，可喜可贺，可喜可贺。 虽然这样很好想，可具体实现似乎有点麻烦，遂

题目传送门 代码实现和一些思路参考了一些题解。 遇到这种序列上研究大小的序列问题，应该主动考虑笛卡尔树。 对原序列建出一棵大根笛卡尔树。稍微转化一下问题的连边条件，首先每个节点必定和它的左子树同在所有点在同一个连通块，这样初步连边后可以看出连通块与连通块之间通过树上右链（从根一直向右走的链）的边进行

题目传送门 这题十分的顺，应该属于能一眼瞪出来的题。 首先不定数个整数异或和最大最好办法 (也有可能是唯一办法？) 就是线性基了。然后是树上路径查询问题，基本方法有两种：1. 处理每个点到根，从问题或点的性质入手，需要挖掘性质。 2.树剖，预处理加上暴力查询，相对无脑。 可以先看看简单的树剖，其做法

题目传送门 卧槽这题有点牛逼。 像我这种蒟蒻只看题面肯定没有什么头绪，所以只好看一眼数据范围，似乎只能依赖方案在 O(m\log) 内解决。 至于为什么会想到 dp ，应该只能靠感觉吧，这题一看就很有线性dp的味道。 所以由前面的想法可以大概先设个 f_i ，至于 i 的含义只能结合方案的性质和所求

题 Sol 应该存在一种经典技巧吧，就是那种可行性DP通过某种手段（感觉最常见的是贪心）压缩一个状态维度。 看到这个题首先应该有个 \texttt{native} 的想法（基于经验？）：考虑设 f_{i,j} 为考虑前 i 个灯笼，能覆盖前缀 [1,j] 的可行性。 然后这里估计能列个方程吧，又或者

转化的基本方向： 复杂 -> 简单 性质少 -> 性质多 序列 单个元素 研究一个元素 x 和整个序列的偏序关系可将每个元素按 >x ， <x 化为 1,0 可将一个元素变为一个坐标点 (index,x) 区间 可将一个区间

From zxy的思维技巧 而来。 传送门 这真是一道套路的好题啊。 首先要计算二元组 (a,b) 的个数，看数据范围肯定枚举一个 a ，然后计算所有满足的 b ，最后求和后除以 2 。 然后具体的考虑怎么计算所谓 b 的个数，考虑一个点 u ，

重链剖分剖分方式 重链剖分的剖分方式是：每次选择子树中最大的子树作为重儿子，其余的子树作为轻儿子。而重链是指一条从根节点到当前节点的路径上，出根节点外，链上其他节点都是重儿子的连边构成的链。如下图： 图中的红色边就是重链，而黑色边就是轻链。每个叶子节点也有一条以自己为起点，长度为 0 的重链。 从图

朴素算法求LCA 首先将深度较大的节点沿着父亲向上跳转，与另一点深度相同后同时跳转，直至跳到同一父亲 int lca(int u, int v) { if (depth[u] < depth[v]) { swap(u, v); } while (depth[u

离散对数问题 假设有一个同余方程a^x \equiv b \pmod m，其中a,b,m都是给定的整数，a与m互素。如何求解x的值？ 第一个想法可能是暴力枚举，将x从0开始枚举到m-1，直到找到一个满足方程的x。时间复杂度是