回文路径

枚举回文中心在哪一行的哪个位置，那么在这一行的回文串一定是取的越长越好，可以直接二分哈希。

正方形计数

枚举一条 $(x,y)$ 向量表示第二个点与第一个点之间的位移，满足 $x+y>0$，计算包含这个向量的合法正方形的个数。

把其他三个点相对于第一个点的位移都求出来，关于 $n$ 个半平面可以得到新的 $n$ 个半平面。

求出半平面交之后，可以得到若干 $ax+by+c\geq 0$ 的限制，使用一些差分的手段后可以转化成求一个 $[0,MAX]\times [0,MAX]$ 的矩形与一个半平面的交形成一个三角形，求这个三角形中的整点个数，由于斜率只有 $n$ 种，进行 $n$ 遍前缀和即可。

独立

树上最大权独立集的经典做法是设 $dp_{k,0/1}$ 表示 $k$ 这个位置是否被选中，不难发现有 $\max(dp_{k,0},dp_{k,1})-dp_{k,0}\leq V$。

考虑设 $siz_k$ 表示 $k$ 子树的大小，设 $f_{k,i}$ 表示 $k$ 子树内，$\max(dp_{k,0},dp_{k,1})-dp_{k,0}=i$ 的方案数。那么有答案为 $\sum_k\sum_i f_{k,i}\times i \times m^{n-siz_k}$。

可以证明 $f_{k,i}$ 在当 $i\not = 0$ 的时候是关于 $i$ 的一个 $siz$ 次多项式，因此考虑拉格朗日插值。

考虑 $u$ 转移到 $k$ 的时候是个减法卷积，因此我们试图求出 $f_{k,m-siz_k...m}$，这可以直接减法卷积。这部分复杂度是 $\sum siz_k\log siz_k$ 的。

接着我们直接使用 $f_{k,m-siz_k...m}$ 点值平移出 $f_{k,1...siz_k}$。这样就能够继续转移到 $k$ 的父亲了。求答案就用 $f_{k,i}\times i \times m^{n-siz_k}$ 的前缀和插一下就行了。同样的 $f_{k,0}$ 的处理也可以拉插，当 $u$ 转移到 $k$ 时（$f'_k\otimes f_u\rightarrow f_k$），把 $\{f'_{k,i}\times (\sum_{j=i}f_{u,j})\}$ 弄几个能算的出来拉插就能转移到新的 $f_{k,0}$ 了，当然还要加上 $f'_{k,0}$ 的贡献，不过处理方式是一样的。

因此整个题可以做到 $O(n^2\log n)$ 的时间复杂度。

分流器

二分答案 $ans$，设 $f_i$ 表示 $i$ 被访问到的次数，那么接下来一定两条出边会各被访问一半，也就是 $f_{out_{i,0}}+=\frac{f_i}{2}$，$f_{out_{i,1}}+=\frac{f_i}{2}$。在过程中判一下是否满足每个点是奇数即可，用 ull 压位高精时间复杂度 $O(\frac{n^3}{w})$。

注意到 $ans$ 只有 lowbit 有用，所以答案一定是 $2$ 的某个次幂，二分指数即可做到时间复杂度 $O(\frac{n^2\log n}{w})$，可以通过。

upd：也可以不需要二分，直接求 $ans$ 为 $2^n$ 的时候每个点的 lowbit 的最小值即可。

排队

扫描线，每个询问在左端点处插入，右端点处查询。

因为询问初始给的初值均为 $0$，因此先插入的询问在同一个右端点处的答案不会比后插入的要小。

因此，将询问按左端点排序，每次的操作形如找到一个区间满足区间内的值都在 $[l,r]$ 内，然后集体 $+1$，可以在树状数组上二分实现。

时间复杂度 $O(n\log n)$。

最短路径

？