T1 食堂计划
最短路图是一张拓扑图，并且只要再这个图上走出的路径就一定是最短路。
于是考虑一个 $dp$ ：设 $dp[u][v]$ 表示当前一个路径结尾在 $u$ 另一个在 $v$ 的方案数量。但是直接转移会出现重点。
我们考虑转移的时候限制如果从 $(u,v) \to (x,v)$ ，必须要有 $dis_u < dis_v \or (dis_u = dis_v \and i < j)$ 才行。唯一可能走出重点的情况就是其中一个点走到了一个根到 $v$ 路径上的点，但是如果这种情况真的出现了，那么之前在 $(x,u)$ 的时候就已经该由 $u$ 去转移，就不会通过这个状态转移到 $(u,v)$ ，也就是说 $x$ 并不在根到 $v$ 路径上。
但是有一种非常套路的解法，考虑设 $dp[u]$ 表示所有到达 $u$ 的路径带上容斥系数的和。具体地说，对于两条到达 $u$ 的路径，如果我们钦定了 $k$ 个点这两个人走到了一起，那么这对路径的系数就是 $(-1)^k$ ，其他位置可以到一起也可以不。
转移就是枚举一个之前的点，然后考虑多钦定一个点，中间随意选择两条路径就好，只需要对于任意两点处理出这两点间的路径条数。
两个做法都写了代码。
T2 笛卡尔树
考虑对于一个长度为 $n$ 的排列，我们钦定最大值位置在 $j$ 后，就确定了其左右两个区间的长度。于是把权值拆开，考虑左右区间长度分别为 $a,b$ ，那么我们考虑怎么合并成对整个区间的贡献。
首先，子树内部的贡献。由于贡献的形式是差值，所以不存在位置带来的影响，所以子树自己的贡献就是
然后考虑如果 $a,b > 0$ 我们需要计算出两个儿子自己的贡献。
考虑所有长度一定的排列中最大值出现位置的和。我们知道
于是分别考虑所有可能的左右排列的贡献。左边的贡献显然是 $-B_a b!$ 但是右边，由于位置有一个便宜量 $j$ ，所以实际上是
但是分配编号还有一个组合数 $\binom{a+b}{a}$ ，于是总的来说，贡献是
然后就可以愉快地 $O(n^2)$ 辣！
假装 $i$ 为我们要算的长度，我们把 $a = j-1 , b = i - j$ 代入 $a,b$ 化下式子
设 $H_i = \frac{A_i}{i!}$ 即可递推。
T3 序列翻转
不是很想改，强行拼题
T4 路径大小差
我们设 $F(l,r)$ 表示边权在 $[l,r]$ 内的路径条数，而设 $G(l,r)$ 表示最小权为 $l$ 最大权为 $r$ 的路径条数的话，可以发现这两个之间是可以容斥得到的。
我们把 $G(l,r)$ 放在二维平面的 $(l,r)$ 上，然后 $F(l,r)$ 就是一块三角形的总和，然后可以容斥一下，发现：
然后就只需要统计 $F$ 了！
首先可以对于 $k,k-1,k-2$ 长度的所有区间分别求，这个东西可以直接拿 LCT 维护，复杂度 $O(n\log n)$ 。
离线下来后可以线段树分治，可撤销并查集即可。复杂度 $O(n\log^2 n)$ 。
由点分 + 二维数点的做法，无限期咕咕咕，可以看翠老师提交。