总的来说这场比赛打完感触还是蛮深的.
深切体会到了背模板的意义
$T1$
$s$到$t$的路径上所有点显然一定会走到，以$s$为根时$t$子树中的点显然走不到，而其它点都有$\frac{1}{2}$的概率会走到。
时间复杂度$O(n log_2{n} + m)$
$T2$
n较小时，我们可以直接用线性筛/埃氏筛法求出每个数的最小质因数。
考虑进行容斥。对于每个质数$x$，我们需要求出$1$~$n/x$中不被比$x$小的质数整除的数的个数。一种简单的思路是，对于$x \leq k$的情况，我们进行常见的枚举子集容斥；对于$x>k$的情况，$n/x$较小，我们就在$n/k$的范围内进行线性筛/埃氏筛法。
注意到进行子集容斥时，枚举子集后贡献形如$(-1)^i·\frac{n}{S}$，而$\frac{n}{S}$只有$O(\sqrt n )$种取值，可以对这个进行记忆化。
复杂度$\frac{n^{\frac{3}{4}}}{\sqrt{log_2 n}}$
$T3$
点分治统计树上的情况，然后单独考虑经过剩下那条边的答案。
在环上按顺序枚举一个端点，用树状数组维护另一个端点到这条边的距离。
时间复杂度$O(nlog_2n)$
总的来说，T1T3的思路基本都有，但是因为代码能力有限，写的题太少，没写出来。。。