T1

字符串基础练习，时间复杂度 $O(nL)$ 。

T2

BFS 洪水填充，但是如果你直接暴力枚举一个点进行拓展的话显然不对。我们可以通过多源 BFS 来做到 $O(nm)$ 。

注意这里必须 $O(nm)$ ，记得以后一定要计算复杂度，不然会被卡常。

更唐的做法：

观察一组合法的三元组的格式是怎样的，显然这三元组因为在树上，故必然存在一个点使得到这三个点距离相等(距离不等反而赢了）。如果不认为显然的请列方程计算，你会发现有解情况唯一剩下的都有环。

那么我们可以枚举交点，把它提起来作为根，然后我们枚举距离 $t$ ，对每一个孩子的子树求其子树内有多少距离根节点为 $t$ 的点，记一个孩子子树的合法点个数为 $a_{i}$ 。

那么答案就是三个不同子树的点进行配对 $\sum\limits_{i\neq j\neq k} a_{i}a_{j}a_{k}$ 。不难发现上述过程光枚举就花了 $O(n^2)$ ，这个玩意还是 $O(n^3)$ 的，我们很成功的只有 $25$ 分，而且是 $O(1)$ 进行计算很难泵。

然后考虑怎么优化这个答案统计过程，发现及其难以优化。但是发现这具有组合意义，考虑容斥计算。

首先记 $sum1=\sum\limits_{i}a_{i}$ ，那么任意选三个点的方案数就是 $\dbinom{sum1}{3}$ 。显然这个方案包含了同子树的，我们要把他们减去：

故答案 $\dbinom{sum1}{3}-\sum\limits_{i} \dbinom{a_{i}}{2} \cdot (sum-a_{i})-\sum\limits_{i}\dbinom{a_{i}}{3}$ 。

直接开始化简！

第一个式子： $\dbinom{sum1}{3}=\dfrac{sum(sum-1)(sum-2)}{6}$ 。
第二个式子： $\sum\limits_{i} \dbinom{a_{i}}{2} \cdot (sum-a_{i})=\dfrac{a_{i}-(a_{i}-1)}{2} (sum-a_{i})$ 。
第三个式子： $\dfrac{a_{i}(a_{i}-1)(a_{i}-2)}{6}$

第二个式子和第三个式子：

\begin{aligned} & =\dfrac{a_{i}(a_{i}-1)}{2}(sum-a_{i})+\dfrac{a_{i}(a_{i}-1)(a_{i}-2)}{6} \\ & = \dfrac{a_{i}(a_{i}-1)}{6}(3(sum-a_{i})+(a_{i}-2)) \\ & = \dfrac{a_{i}(a_{i}-1)}{6}(3sum -2a_{i} -2) \end{aligned}

原式即为：

\dfrac{sum(sum-1)(sum-2)}{6}-\sum\limits_{i} \dfrac{a_{i}(a_{i}-1)}{6}(3sum -2a_{i} -2)

进一步化简：

\dfrac{1}{6}[sum(sum-1)(sum-2)-\sum\limits_{i} a_{i}(a_{i}-1)(3sum-2a_{i}-2)]

考虑后式，记 $sum_{2}=\sum\limits_{i}a_{i}^2,sum_{3}=\sum\limits_{i}a_{i}^3$ 。有：

\sum\limits_{i} a_{i}(a_{i}-1)(3sum-2a_{i}-2)=\sum\limits_{i}(3sum\cdot a_{i}^2-(3sum-2)a_{i}-2a_{i}^3)

进一步化简代回分子式有：

sum(sum-1)(sum-2)-(3sum\cdot sum_{2}-(3sum -2)\cdot sum-2sum_3)

最后化简有：

ans=\dfrac{sum^3 -3sum\cdot sum_{2}+2sum_{3}}{6}

即可 $O(1)$ 计算，用 BFS 按层计算，时间复杂度 $O(nm)$ ，推式子时长占到了总时长的 90%，据观察没有人会想我这么唐推这个式子，直接一开始不等距离也是可以直接做的，反而会更简单直接组合数即可。

总结：不要看到式子就星宇大发，一定要冷静观察有没有更好的做法。

T3 太唐了没有分配好时间去做。推完式子发现没时间做了，以后要有时间意识。

卡常，卡常，卡常！