{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:25.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/e2c799fd03121ad54f98baf17fc72b14?v\u003d1714904424\" alt\u003d\"/problems/perfectpathpatrol/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003ePleasantville is a community that appreciates simplicity.\n We can view the road network in Pleasantville as a collection\n of junctions that are connected by two-way streets. This has\n been done in a simple manner: there is precisely one way to\n travel between any two junctions in Pleasantville without\n traversing any street more than once.\n \u003cp\u003eCitizens have formed a community watch program to ensure the\n streets are safe to walk at night. So, some citizens patrol\n certain regions of the neighborhood. These patrols are also\n simple: a single citizen simply patrols all streets lying on\n the unique path between two junctions assigned to them.\u003c/p\u003e\n \u003cp\u003eEach street \u003cspan class\u003d\"tex2jax_process\"\u003e$e$\u003c/span\u003e also\n has a simple criterion: exactly \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ e$\u003c/span\u003e patrollers must include street\n \u003cspan class\u003d\"tex2jax_process\"\u003e$e$\u003c/span\u003e in their patrol path.\n If fewer than \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ e$\u003c/span\u003e\n patrollers were assigned to cover street \u003cspan class\u003d\"tex2jax_process\"\u003e$e$\u003c/span\u003e, then it might not be safe. If\n more than \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ e$\u003c/span\u003e\n patrollers were assigned to cover street \u003cspan class\u003d\"tex2jax_process\"\u003e$e$\u003c/span\u003e, the citizens themselves might\n become uneasy with the heightened presence of patrollers.\u003c/p\u003e\n \u003cp\u003eYou have been tasked with organizing this community watch\n program. Of course, it is ideal to minimize the number of\n patrollers you use. Thus, you must enlist the fewest possible\n patrollers and assign each to a path between two junctions in\n the neighborhood such that any street \u003cspan class\u003d\"tex2jax_process\"\u003e$e$\u003c/span\u003e lies on exactly \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ e$\u003c/span\u003e patrollers’ paths.\u003c/p\u003e\n \u003cdiv id\u003d\"a0000000004\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/bd070fe396554dc663a3909ebfd406f7?v\u003d1714904424\" alt\u003d\"\\includegraphics[width\u003d0.5\\textwidth ]{figure/perfectpathpatrol.pdf}\" style\u003d\"width:50.00%\"\u003e\n \u003c/center\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: An illustration of the first sample. The\n numbers by the solid black edges indicate how many\n patrollers must include that edge in their paths. The\n dashed red curves indicate one possible way to select\n \u003cspan class\u003d\"tex2jax_process\"\u003e$10$\u003c/span\u003e patrol paths so\n every edge lies on exactly the required number of patrol\n paths. That is, one solution is to use \u003cspan class\u003d\"tex2jax_process\"\u003e$10$\u003c/span\u003e patroller paths with\n endpoints: \u003cspan class\u003d\"tex2jax_process\"\u003e\\[ (5, 2), (6, 0),\n (6, 3), (4, 2), (4, 0), (4, 0), (4, 0),(1, 2), (2, 3), (2,\n 3) \\]\u003c/span\u003e It is impossible to use fewer than 10\n patrollers while ensuring each street is patrolled by\n exactly the required number of patrol paths.\n \u003c/div\u003e\n \u003c/div\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of input contains a single value \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2\n \\leq N \\leq 500\\, 000$\u003c/span\u003e) indicating the number of\n junctions in the neighborhood, which are numbered \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e through \u003cspan class\u003d\"tex2jax_process\"\u003e$N-1$\u003c/span\u003e.\u003c/p\u003e\n \u003cp\u003eThen \u003cspan class\u003d\"tex2jax_process\"\u003e$N-1$\u003c/span\u003e lines\n follow, each containing three integers \u003cspan class\u003d\"tex2jax_process\"\u003e$u,v,p$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq u,v \u0026lt; N$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq p \\leq 10^9$\u003c/span\u003e). This indicates\n there is a street connecting junction \u003cspan class\u003d\"tex2jax_process\"\u003e$u$\u003c/span\u003e to junction \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e and that this street must lie on\n exactly \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e patrol\n paths.\u003c/p\u003e\n \u003cp\u003eYou are guaranteed there is a unique way to travel between\n any two junctions using the provided streets.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput a single line with a single integer indicating the\n minimum number of patrollers you need to enlist for the\n community watch program.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7\n0 1 3\n1 2 5\n1 3 3\n0 4 7\n4 5 1\n4 6 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n0 1 1\n0 2 1\n0 3 1\n1 4 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}