SP24191 EAGLE1 - Eagle and Dogs

Eagle（化名 Mohamed Ahmed）住在一个由 **n** 个交叉口和 n-1 条道路组成的城市中。这些道路的连接方式使得他可以从任何一个交叉口到达另一个交叉口。 Eagle 每天都会在城市中散步，并遵循一条简单的策略：在一个交叉口时，他必须随机选择一条尚未走过的道路并沿路前行；如果所有道路都走过一遍，他就停止行走并回家。 可他有个问题，他很怕狗，甚至不喜欢看到狗。因此，他想知道最坏的情况下，如果他从某个交叉口开始散步，他会遇到多少只狗。你能帮助他解决这个问题吗？

输入首先是一个整数 **T** (1 ≤ **T** ≤ 10)，表示测试用例的数量。接下来的 T 个部分分别描述每个测试用例。 每个测试用例的第一行包含一个整数 **n** (2 ≤ **n** ≤ 10 $ ^{5} $ )，表示城市中的交叉口数量。交叉口的编号为 1 到 n。 随后有 n-1 行，每行包含三个整数 **u**, **v** 和 **d** (1 ≤ **u**, **v** ≤ **n**, 1 ≤ **d** ≤ 10 $ ^{9} $ )，分别表示这条道路连接的两个交叉口以及 Eagle 在这条道路上会看到的狗的数量。

对于每个测试用例，输出一行，包含 n 个整数。第 i 个整数表示如果 Eagle 从第 i 个交叉口开始散步，他可能会遇到的狗的最大数量。 **本翻译由 AI 自动生成**