这里用于记录我想记录的任何东西。
每日学习（虚树边权和）
考虑树上任意 $k$ 个点 $a_1,a_2\cdots a_k$，包含他们的最小连通子树的边树（也即他们的虚树边权和）可以用如下方式求出：
考虑将 $k$ 个点按照 dfn 序从小到大排列为 $p_1,p_2\cdots p_k$，特别的，钦定 $p_{k+1}=p_1$，则虚树边权和等于 $\frac{\sum_{i=1}^k \text{dist}(p_i,p_{i+1})}{2}$，其中 $\text{dist}(i,j)$ 表示树上 $i,j$ 两点最短路径的边数。
每日学习（有关约数个数函数的公式）
记 $d_n$ 表示 $n$ 的约数个数。
有 $d_{ij}=\displaystyle\sum_{x\mid i}\sum_{y\mid j}[x\perp y]$，其中 $\perp$ 表示互质。
证明直接考虑在 $ij$ 的任意一个约数和 $(x,y)$ 之间构造双射即可。
位运算卷积指，给定两个长度为 $n$ 的数组 $a,b$，0-index，求数组 $c=a*b$ 满足 $c_k=\displaystyle\sum_{i\otimes j=k}a_i\times b_j$，其中 $\otimes$ 表示一种位运算。 分治乘法解决此类问题的思想是，对于任意一种位运算而言，不同的位之间互不影响，所以可以通过某种方式去…
题目是 AT_abc306_g [ABC306G] Return to 1 - 洛谷。 以下所有叙述均不考虑自环、重边。 上题本质上要求求出所有经过点 $1$ 的环环长的 gcd。 首先把包含点 $1$ 的强连通分量拿出来，显然只用考虑这个子图即可。 接下来考虑以 $1$ 为根建立任意一棵 dfs 搜索树，我们不加证明地给出一个断言：答案等于 $\…
散题 换根 DP： P3647 [APIO2014] 连珠线 - 洛谷 P2081 [NOI2012] 迷失游乐园 - 洛谷 树形 DP： AT_abc340_g [ABC340G] Leaf Color - 洛谷 P4253 [SCOI2015] 小凸玩密室 - 洛谷 P3687 [ZJOI2017] 仙人掌 - 洛谷 AT_agc034_e […
每日学习（常见 trick 之变换坐标轴）
典题是 AT_abc221_g [ABC221G] Jumping sequence – 洛谷。
另一个典题 AT_abc240_g [ABC240G] Teleporting Takahashi – 洛谷。
本题中，题面要求我们解决两个事情：决策 $D_i$ 分配给横坐标还是纵坐标，以及加还是减。
这个显然是不好做的，这就可以引出一种常见 trick。
考虑把 $(X,Y)\to(X+Y,X-Y)$，这显然是一个双射，我们可以发现原来的操作变成了：
- 向上：$(X,Y)\to(X+D,Y-D)$
- 向下：$(X,Y)\to(X-D,Y+D)$
- 向左：$(X,Y)\to(X-D,Y-D)$
- 向右：$(X,Y)\to(X+D,Y+D)$
容易发现这样我们不再需要决策 $D_i$ 分配给谁，同时横纵坐标对于每个 $D_i$ 而言的加减情况完全独立，只需要分开解决即可，显然可以使用 bitset 优化背包。
事实上，$(X,Y)\to(X+Y,X-Y)$ 是一种经典的 trick（在曼哈顿与切比雪夫的互相转化中亦有记载），他的本质是通过把横纵坐标结合起来减少限制，当发现题目中横纵坐标互相限制时，可以尝试使用此技巧。