Creator's World

总结在做题时遇到的一些题型。

题型：动态修改、查询 边权。

知识点：树链剖分。

解决方法：
将边权看作一条边的 子节点（深度较深）的点的权值。

注意点：两点跳到同一条链上时，在上面的点是两者的 LCA，其自己的值不用修改 / 查询，而应从其 $+1$ 的点开始。

例题：P4114 Qtree1、P3038 [USACO11DEC]Grass Planting G

题型：给定 $y,z,p$，求 $xy \equiv z \pmod p$ 的解 $x$。

知识点：exgcd。

解决方法：将原式转化为 $xy + pk = z$，再用 exgcd 求出 $x$。

题型：有一棵树，定义 $f_{i,j}$ 表示 $i$ 到 $j$ 路径上边权的最大值，$g_{i,j}$ 表示 $i$ 到 $j$ 路径上边权的最小值。求 $\sum_{i=1}^{n}\sum_{j=i}^{n}f_{i,j}-g_{i,j}$。

知识点：并查集。

解决方法：

• 最大值

1. 将边按权值 从小到大 排序；

2. 对于每一条边对答案的贡献为 $e_i.val \times size_{fx} \times size_{fy}$；

3. 若 $fx\ne fy$，合并，$fa_{fx} = fy,size_{fy}+=size_{fx}$。

• 最小值

  类似，只是按边权 从大到小 排序。

原理：其实还是好想的，以最大值为例，考虑第 $i$ 条边权会成为几次最大值。边权从小到大排序，显然前面满足的后面一定满足。最小值同理。

拓展：求最大 $/$ 最小 点权。

解决方法：每条边的最大值 $e_i.maxn=\max(a_{e_i.from},a_{e_i.to})$。最小值同理。

原理：因为自己取 $\max$ 并不会有影响。

例题：CF915F Imbalance Value of a Tree

题型：在数轴上有一些点有权值，你需要左右移动以获得点上的权值，问获得的最大权值 $/$ 获得所有值的最小时间等。

解决方法：区间 dp。用到贪心的思想，对于一个区间一定走到底，要么走到最左，要么走到左右。因此设 $f_{i, 0 / 1}$ 表示走到了左边 $/$ 右边的值。

原理：因为经过了一个点取它比不取一定更优，一定不会折回来。

例题：2021.5.7 模拟赛 T3。区间 dp 的模型是简单的，但是具体的转移还是没有搞懂。