P1079盈盈一水间（town）

【题目背景】

路标台恢复后，车队得以穿过通向铜炉山的内陆河谷。河谷中的古镇被支路与水道分隔，Ehundategh 决定在离开前完成一次不重复经过任何古镇的巡查。

【题目描述】

河谷中共有 $n$ 个古镇，依次编号为 $1\sim n$。古镇之间有 $n-1$ 条双向道路，并且任意两个古镇之间都可以通过这些道路互相到达。第 $i$ 条道路连接古镇 $u_i,v_i$，经过这条道路需要 $w_i$ 个单位时间。

Gioush 大队最初位于河谷入口的 $1$ 号古镇。以古镇 $1$ 为根，可以将这些古镇与道路看作一棵有根树。若一个古镇在这棵树中没有儿子，则称它为下游古镇。

每个下游古镇旁都设有通向水道的渡口。当 Gioush 大队抵达任意一个下游古镇时，可以乘船直接前往任意另一个下游古镇。水路不经过其他古镇，并且本题只统计道路上的巡查时间，因此一次水路转移的时间记为 $0$。

Ehundategh 希望从古镇 $1$ 出发，经过其余每个古镇恰好一次，最后回到古镇 $1$。在回到古镇 $1$ 之前，巡查过程中不能再次经过古镇 $1$。

道路越长，能够留下的巡查记录越多。请你求出所有合法巡查中经过道路的时间总和的最大值。若不存在合法巡查，输出 Pity!。

形式化题意：在一棵以 $1$ 为根的带权树中，为任意两个叶子补充一条权值为 $0$ 的边，求一条从 $1$ 出发并回到 $1$、恰好经过每个非根结点一次的闭合路径的最大权值，或判断这样的路径不存在。

【输入格式】

从文件 $\textbf{\textit{town.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含一个非负整数 $c$ 与一个正整数 $T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含一个正整数 $n$，表示古镇数量。

接下来 $n-1$ 行，第 $i$ 行包含三个整数 $u_i,v_i,w_i$，表示第 $i$ 条道路连接的两个古镇以及经过这条道路所需的时间。

【输出格式】

输出到文件 $\textbf{\textit{town.out}}$ 中。

对于每组测试数据输出一行。若存在合法巡查，输出能够得到的最大时间总和。若不存在，输出 Pity!。

【样例 1 输入】

10 22931 2 141 3 151 4 161 5 172 6 183 7 194 8 1105 9 1115121 3 2131 4 5141 2 3152 5 6

【样例 1 输出】

1Pity!214

【说明/提示】

【样例 1 解释】

第一组测试数据不存在合法巡查。

第二组测试数据中，可以依次经过古镇 $1,4,3,5,2,1$。其中从古镇 $4$ 到古镇 $3$、从古镇 $3$ 到古镇 $5$ 均通过水路转移，经过道路的时间总和为 $5+6+3=14$。可以证明不存在时间总和更大的合法巡查。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 5$，$3\leq n\leq 2\times 10^5$，$1\leq u_i,v_i\leq n$，$0\leq w_i$，$\sum w_i\leq 10^9$。对于同一个测试点，保证 $\sum n\leq 2\times 10^5$。

特殊性质：保证所有道路的权值均为 $0$。