t1:

二分答案+贪心判定。

t2:

$f[i][j][k]$表示用了$i$段，两个串分别用到了前$j$,$k$位的方案数。从这一位开始枚举向前取几位。 容易发现预处理一下公共串长就可以前缀和优化了。时间复杂度$O(nmk)$。

最后一个点似乎被卡了常数，不过也可能是考场电脑太慢...

t3:

倍增预处理每条链的LCA和长度。 二分答案，球出对于超过当前答案的链的交集。在交集中找到权值最大的边判断删掉后是否合法。 找交集可以打标记$O(n)$解决。

最后一个点被卡了常数，不过也可能是考场电脑太慢...

好虚啊，要滚粗啦！