绿色行动 Let's Go Green

# 绿色行动Let's Go Green 绿地王国有很多城市，每个城市都通过道路与其他城市相连。这样，从一个城市到另一个城市，就有了一条路。树地每条路连接两个不同的城市。 这个王国的国王想鼓励他的公民有良好的自然环境意识责任。他的议程之一是推广自行车，一种轮式人力运输，作为公民出行的主要交通工具，而不是摩托车或汽车可能对环境造成严重污染。 为了确定他的竞选进程，国王要求财政大臣监督在王国中，每一条道路上的自行车数量。议长执行了国王的命令立即将结果报告给他的国王，也就是说，在王国的每一条道路上，他都报告了一整天内通过这些道路的自行车数量。国王很高兴，但没过多久是时候让他意识到这份报告可能会产生误导了。报告只说自行车的数量经过每一条路，对当天使用的自行车总数一言不发。它也不包含任何关于报告自行车方向的信息。 例如，考虑下图（左图）所示的城市结构。有两辆自行车经过连接A市和B市的道路，1条连接B市和C市的道路，2条连接C-D市和1条连接C-E市的道路。总计记录的自行车数量是2+1+2+1=6，但并不代表实际的自行车数量使用率为6。在有些情况下，自行车被用来在城市x和z之间穿行其他城市，比如这辆自行车被记录了好几次，在X和Z之间的每条道路上记录一次。右图描述了一种可能性，即只有3辆自行车，其中一辆用于A和B之间的行程，一个用于A和D之间通过B和C的行程，另一个用于D和E之间的行程通过C。 假设没有自行车被用来超过一次通过任何道路。如果道路检测到P超车自行车，那么这些是P不同的自行车。现在你的任务是帮助国王确定报告中使用的最少自行车数量。 输入 输入的第一行包含一个整数t（t≤10），表示事例数。每件事都开始了用一个整数n（2≤n≤100000）表示王国中城市的数量1...。n.接下来的n-1行每行包含三个整数a、b和c（1≤a，b≤n；a=b；0≤c≤100）表示记录有C辆自行车通过连接A和B的道路。注意这条n-1线描述了王国的完整城市结构。 输出 对于每种情况，输出“case x:y”，其中x是案例编号，从1开始，y是最小值。相应情况下使用的自行车数量。 样例 Sample Input 2 5 1 2 2 2 3 1 3 4 2 3 5 1 7 1 2 1 2 3 2 2 4 1 2 5 3 5 6 2 5 7 3 Sample Output Case #1: 3 Case #2: 5

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4543 [PDF](https://uva.onlinejudge.org/external/16/p1668.pdf)