T4 喵喵（meow）

首先能看出这是一道最短路题目。由于最终所有的流浪猫都要聚集到点 $1$，我们运用 Dijkstra 算法求出每个点到点 $1$ 的最短路径改如何走（这里要注意字典序）。

然后来考虑如何求解总时间。先假设不增加捷径。由于所有流浪猫走向点 $1$ 的路径最后会形成一棵树，也就是所谓的最短路径树，我们可以直接建出这棵树，在树上来求解总时间。

求解总时间有两种方法。一是对于每一个点，求从这个点到点 $1$ 的距离，再求和。二是考虑最短路径树上的一条边，求出经过这条边的总猫猫数量，也即是子树内的猫猫数量。

此处使用第二种方式更利于后续分析。现在我们思考如何增加捷径。沿用上文的第二种方法，当子树 $i$ 内的所有猫猫都汇聚在点 $i$，我们在 $1,i$ 之间建立一条捷径后，每只猫猫会少走 $dis_i - t$，其中 $dis_i$ 表示点 $i$ 到点 $1$ 的最短距离。于是，枚举所有点求出节省时间最大值即可。