#81 P11324
题目传送门
考前做到的一道清新树剖题。
考虑 \(x_i=1\) 的部分分。那么首先有固定贡献 \(c_x+c_y-dis(x,y)\)，因此只需要考虑 \(z\) 对答案的贡献。那么对于 \(x \rightarrow y\) 路径上的每一个点 \(u\)，考虑如果点 \(z\) 在 \(u\) 为根的子树内，那么对答案的贡献是多少。那么显然应该是 \(\max \limits_{v\in subtree(u)}c_v-2dis(u,v)\)。然后套路地，将祖孙距离转化为树上差分，记 \(d_u\) 为 \(u\) 到 \(1\) 的距离，原式转化为 \(2d_u+\max \limits_{v\in subtree(u)}c_v-2d_v\)。那么发现对于每一个 \(u\)，上述式子是一个定值，所以直接预处理即可。
那么考虑正解。如果点 \(z\) 在 \(LCA(u,v)\) 的子树内，那么上述方法照样用。所以只需要考虑不在其子树内的情况。然后发现这种情况也只是多了 \(-2dis(LCA(u,v),LCA(u,v,z))\) 的贡献，对每一个点预处理即可。
时间复杂度为 \(O(n\log^2 n)\)。
#82 P10812
题目传送门
正难则反。因为求因数较为困难，所以转化为逆向后求倍数。
Key Observation：每一次进行 \(i-1\) 后，想要增大坐标能且仅能跳倍数。
那么现在情况就简化很多了。定义 \(f_{i,j}\) 表示当前在 \(i\)，最远到过 \(j\) 的方案数。考虑转移：
-
\(f_{i,i} \rightarrow f_{i+1,i+1}\)；
-
\(f_{i,j}\rightarrow f_{i+1,j}\)；
-
\(f_{i,j}\rightarrow f_{x,ki}(j+1\le x\le ki)\)；
最后一种转移显然可以前缀和优化一下。
时间复杂度为 \(O(n^2\sum\limits_{i}\dfrac{n}{i})=O(n^2\ln n)\)，常数较小，可以通过。
#83 P9695
题目传送门
首先，询问本质就是问从一个出发，可以走的最大区间的权值和。
权值的修改和求和是简单的，但是怎么维护颜色是一个问题。
但是发现 \(5s\) 的时间限制对 \(3\times 10^5\) 的数据范围在 \(\log\) 级算法中比较少见，或许可以考虑根号级算法。考虑分块，对于每一个块，预处理块内颜色集，询问时 \(O(k)\) 判断能否通过该块，不能就逐点判断。
取块长为 \(\sqrt{\sum k}\)，时间复杂度为 \(O((\sum k)^{1.5})\)。
#84 P10107
题目传送门
首先，注意到这是一个和深度相关的二进制运算，所以想到“倍增”；其次，答案累计用加法，所以考虑用前缀和。
然后，考虑怎么预处理这个倍增。如果只维护一个点自己子树内的答案，那么统计会很困难。因为需要访问一个点子树内在一个深度上的每一个节点，这非常不方便。考虑一个点维护同深度的点中 dfn 序小于等于自己的点的答案。这是比较方便维护的，因为只需要跳到子树内该深度中 dfn 最大的点即可。
那么记 \(f_{u,i}\) 表示同深度的点中 dfn 序小于等于自己的点的在询问相对深度为 \(2^i\) 时的答案，\(lst_u\) 为同深度中 dfn 小于的自己的点中 dfn 最大的点的编号， \(Pre_u\) 为 \(u\) 的儿子中 dfn 序最大的节点编号，如果没有就为 \(Pre_{lst_u}\)，记 \(pre_{u,i}\) 表示跳 \(2^i\) 次 \(Pre_u\) 后到达的节点编号。
考虑怎么由 \(f_{u,i-1}\) 转到 \(f_{u,i}\)。那么就是要把 \(pre_{u,i-1}\) 上深度为 \(2^{i-1}\) 中的节点都异或上 \(2^{i-1}\)。为了维护权值变化，记 \(cnt_{u,i}\) 表示深度相对深度小于等于 \(2^i\) 时内的 dfn 序小于等于自己子树内 dfn 序最大的节点的节点个数。
那么转移就是正常的倍增。
#85 CF757G
题目传送门
如果无修，那么就是 HNOI2015 开店，但是它带修。
那么考虑询问的构成：首先，套路地拆询问为前缀形式；其次，因为 \(dis(u,v)=dep_u+dep_v-2dep_{LCA(u,v)}\)，所以记 \(D_i\) 表示 \(a\) 序列前 \(i\) 个点的深度和，那么询问可以改写为：
只需要考虑后面那部分元素怎么处理即可。考虑它的本质就是 \(a_i\) 和 \(v\) 到根路径上的公共部分，那么可以对每一个 \(a_i\) 让它到根的部分加标记，然后询问时访问 \(x\) 到根的路径上每一条边的标记次数乘边权之和，这是树剖简单题。对于询问一个前缀，那么直接主席树即可。
考虑修改，因为只有邻项，所以考虑直接在可持久化线段树上修改即可。
时间复杂度和空间复杂度均为 \(O(n\log^2n)\)。
#86 P7600/CF1119F
题目传送门
考虑 \(O(n^2\log n)\) 算法。
套路地，定义 \(f_{u,0/1}\) 表示已经处理完了 \(u\) 子树内所有限制，并且不删/删 \(u\) 到其父亲的边。约定 \(d_u\) 是 \(u\) 的度数，\(v\) 是 \(u\) 的某一个儿子。
那么在 \(u\) 点时考虑怎么转移：先钦定每一个儿子都不选并计算权值，然后按 \(f_{v,1}+w(u,v)-f_{v,0}\) 排序，选择其中前 \(d_u-x\) 大的权值即可。（如果在转移 \(f_{u,1}\)。则需要少选一个）
那么观察上述形式，发现对于每一个 \(x\) 的计算，相同步骤其实非常多，因此考虑能否利用之前的信息。那么有一个观察：若 \(d_v\le x\)，那么 \(v\) 对父亲 \(u\) 的贡献要么是 \(0\)，要么是 \(w(u,v)\)。这很好解释，因为 \(v\) 自己没有删边的需求。
称度数大于 \(x\) 的点为有用的，其余的为无用的。如果每次只处理有用点，那么时间复杂度为 \(O(\sum d_i\log d_i)=O(n\log n)\) 可以接受。
从小到大枚举 \(x\)，如果一个点 \(u\) 此时从有用点变成无用点，那么就在树上删掉它，并对每一个邻居 \(v\) 的权值数组里加入 \(w(u,v)\)。然后就和之前一样进行 dp。计算结束后，将有用点对父亲的贡献从父亲的权值数组里删去。
或许可以用平衡树实现，时间复杂度为 \(O(n \log n)\)。