在这座树形城市中,有 n 个节点互相连接,每个节点可以作为一座城市的代表。塔子哥是这座城市的管理员,他一直关注着这座城市的安全和交通状况。
但是最近,城市中的一些道路因为年久失修、自然灾害等原因出现了断裂,这导致了交通的瘫痪和城市的分裂。为了解决这个问题,塔子哥决定组织一支维修队来修复这些断裂的道路。
维修队会从城市中的出发点 1 出发,一个维修队从 1 出发到一个点,路上所有断边都会被修好。
塔子哥想知道最少需要多少个维修队,才能修复好整座城市的断边。
输入第一行为一个整数 n ,( 1≤n≤105 )
接下来 n−1 行,每一行有三个整数 u,v,z。1≤u,v≤n, z=1 代表 u 到 v 的边为断的, z=0 代表 u 到 v 的边是好的。
输出最少需要多少个修理队,能修复好整座城市的断边。
输入
4
1 2 0
1 3 1
2 4 0
输出
1
输入
5
1 2 1
1 3 0
2 5 1
3 4 1
输出
2
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.