Perfect Path Patrol

Image by paulbr75 from Pixabay
Pleasantville is a community that appreciates simplicity. We can view the road network in Pleasantville as a collection of junctions that are connected by two-way streets. This has been done in a simple manner: there is precisely one way to travel between any two junctions in Pleasantville without traversing any street more than once.

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.

\includegraphics[width=0.5\textwidth ]{figure/perfectpathpatrol.pdf}
Figure 1: An illustration of the first sample. The numbers by the solid black edges indicate how many patrollers must include that edge in their paths. The dashed red curves indicate one possible way to select $10$ patrol paths so every edge lies on exactly the required number of patrol paths. That is, one solution is to use $10$ patroller paths with endpoints: \[ (5, 2), (6, 0), (6, 3), (4, 2), (4, 0), (4, 0), (4, 0),(1, 2), (2, 3), (2, 3) \] It is impossible to use fewer than 10 patrollers while ensuring each street is patrolled by exactly the required number of patrol paths.


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 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
0 1 3
1 2 5
1 3 3
0 4 7
4 5 1
4 6 2
Sample Input 2 Sample Output 2
0 1 1
0 2 1
0 3 1
1 4 1
CPU Time limit 4 seconds
Memory limit 1024 MB
Difficulty 6hard
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in