Problem E
Perfect Path Patrol
Citizens have formed a community watch program to ensure the streets are safe to walk at night. So, some citizens patrol certain regions of the neighborhood. These patrols are also simple: a single citizen simply patrols all streets lying on the unique path between two junctions assigned to them.
Each street $e$ also has a simple criterion: exactly $p_ e$ patrollers must include street $e$ in their patrol path. If fewer than $p_ e$ patrollers were assigned to cover street $e$, then it might not be safe. If more than $p_ e$ patrollers were assigned to cover street $e$, the citizens themselves might become uneasy with the heightened presence of patrollers.
You have been tasked with organizing this community watch program. Of course, it is ideal to minimize the number of patrollers you use. Thus, you must enlist the fewest possible patrollers and assign each to a path between two junctions in the neighborhood such that any street $e$ lies on exactly $p_ e$ patrollers’ paths.
Input
The first line of input contains a single value $N$ ($2 \leq N \leq 500\, 000$) indicating the number of junctions in the neighborhood, which are numbered $0$ through $N-1$.
Then $N-1$ lines follow, each containing three integers $u,v,p$ ($0 \leq u,v < N$, $0 \leq p \leq 10^9$). This indicates there is a street connecting junction $u$ to junction $v$ and that this street must lie on exactly $p$ patrol paths.
You are guaranteed there is a unique way to travel between any two junctions using the provided streets.
Output
Output a single line with a single integer indicating the minimum number of patrollers you need to enlist for the community watch program.
Sample Input 1 | Sample Output 1 |
---|---|
7 0 1 3 1 2 5 1 3 3 0 4 7 4 5 1 4 6 2 |
10 |
Sample Input 2 | Sample Output 2 |
---|---|
5 0 1 1 0 2 1 0 3 1 1 4 1 |
2 |