{"trustable":false,"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":"\u003cp\u003eThe Galactic Empire consists of many planets, but interstellar traveling is difficult even in the future. Traveling is only possible through special two-way portals, but these portals are expensive to build, so the \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e planets (numbered from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e) are connected by \u003cspan class\u003d\"tex2jax_process\"\u003e$n - 1$\u003c/span\u003e portals, such that there is exactly one simple path between any pair of planets.\u003c/p\u003e \n\u003cp\u003eAll planets are dependent on an important resource, \u003cem\u003espice\u003c/em\u003e, which only the emperor has access to. The emperor made plans to distribute the spice to the \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e planets: the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-th planet will receive \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i$\u003c/span\u003e units of spice.\u003c/p\u003e \n\u003cp\u003eHowever, the citizens feel that the plan is not fair. They submit \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e requests. In each request, \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e planets \u003cspan class\u003d\"tex2jax_process\"\u003e$\\ell $\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$u$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e are given, such that the distance from \u003cspan class\u003d\"tex2jax_process\"\u003e$\\ell $\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e and from \u003cspan class\u003d\"tex2jax_process\"\u003e$u$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e are equal. Here the distance from planet \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e to planet \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e is the number of portal passes on the only simple path from \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e.\u003c/p\u003e \n\u003cp\u003eLet \u003cspan class\u003d\"tex2jax_process\"\u003e$p_1 \u003d u, p_2, \\ldots , p_{\\ell } \u003d v$\u003c/span\u003e denote the simple path between planet \u003cspan class\u003d\"tex2jax_process\"\u003e$u$\u003c/span\u003e and planet \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e; \u003cspan class\u003d\"tex2jax_process\"\u003e$q_1 \u003d x, q_2, \\ldots , q_{\\ell } \u003d y$\u003c/span\u003e denote the simple path between planet \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e and planet \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e. The request says that for every \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e between \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$\\ell $\u003c/span\u003e, planet \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ i$\u003c/span\u003e and planet \u003cspan class\u003d\"tex2jax_process\"\u003e$q_ i$\u003c/span\u003e receive the same amount of spice.\u003c/p\u003e \n\u003cp\u003eChanging the spice distribution plan turns out to be a difficult problem. The Emperor has a non-negative integer \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e and he can change the plan by applying the following steps:\u003c/p\u003e \n\u003cul class\u003d\"itemize\"\u003e \n \u003cli\u003e \u003cp\u003eSelect an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e.\u003c/p\u003e \u003c/li\u003e \n \u003cli\u003e \u003cp\u003eSelect a planet \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e.\u003c/p\u003e \u003c/li\u003e \n \u003cli\u003e \u003cp\u003eEither decrease or increase the amount of spice assigned to planet \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e by \u003cspan class\u003d\"tex2jax_process\"\u003e$t \\cdot k + 1$\u003c/span\u003e. In other words, the Emperor can either set \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i :\u003d a_ i + (t \\cdot k + 1)$\u003c/span\u003e or \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i :\u003d a_ i - (t \\cdot k + 1)$\u003c/span\u003e. After this step, \u003cb class\u003d\"bfseries\"\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i$\u003c/span\u003e must be a non-negative integer\u003c/b\u003e, as we cannot distribute negative amounts of spice.\u003c/p\u003e \u003c/li\u003e \n\u003c/ul\u003e \n\u003cp\u003eWhat is the minimum number of actions the Emperor needs to perform to satisfy all the requests?\u003c/p\u003e \n\u003ch2\u003eInput\u003c/h2\u003e \n\u003cp\u003eThe first line of input contains \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e\u0026nbsp;— the number of planets, the number of requests and the integer the Emperor has to change the assignment of spice \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\le n \\le 5 \\cdot 10^5, 1 \\le q \\le 2 \\cdot 10^5, 0 \\le k \\le 10^6)$\u003c/span\u003e.\u003c/p\u003e \n\u003cp\u003eThe second line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e integers, \u003cspan class\u003d\"tex2jax_process\"\u003e$a_1, a_2, \\ldots , a_ n$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\le a_ i \\le 10^9)$\u003c/span\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i$\u003c/span\u003e is the initial amount of spice assigned to planet \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e.\u003c/p\u003e \n\u003cp\u003eThe next \u003cspan class\u003d\"tex2jax_process\"\u003e$n - 1$\u003c/span\u003e lines contain \u003cspan class\u003d\"tex2jax_process\"\u003e$n - 1$\u003c/span\u003e integers \u003cspan class\u003d\"tex2jax_process\"\u003e$p_2, p_3, \\ldots p_ n$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\leq p_ i \u0026lt; i)$\u003c/span\u003e, one on each line, meaning that there is a two-way portal connecting planet \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ i$\u003c/span\u003e and planet \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e.\u003c/p\u003e \n\u003cp\u003eEach of the next \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e lines contains \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e integers \u003cspan class\u003d\"tex2jax_process\"\u003e$u$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e, specifying one request \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\le u, v, x, y \\le n)$\u003c/span\u003e. It is guaranteed that the two simple paths from \u003cspan class\u003d\"tex2jax_process\"\u003e$u$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e and from \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e have equal length.\u003c/p\u003e \n\u003cp\u003eIt is guaranteed that there is exactly one simple path between any pair of planets, and that it is possible to satisfy all \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e requests.\u003c/p\u003e \n\u003ch2\u003eOutput\u003c/h2\u003e \n\u003cp\u003eOutput a single integer\u0026nbsp;— the minimum number of the Emperor needs to perform.\u003c/p\u003e \n\u003ch2\u003eExplanation of Sample input\u003c/h2\u003e \n\u003cp\u003eThere are \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e portals between planets: \u003cspan class\u003d\"tex2jax_process\"\u003e$(1, 2)$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$(1, 3)$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$(3, 4)$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$(3, 5)$\u003c/span\u003e.\u003c/p\u003e \n\u003cp\u003eSince timestep \u003cspan class\u003d\"tex2jax_process\"\u003e$k \u003d 0$\u003c/span\u003e, at each step, the Emperor can either increase or decrease \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i$\u003c/span\u003e by\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e.\u003c/p\u003e \n\u003cp\u003eAn optimal solution would be to reduce \u003cspan class\u003d\"tex2jax_process\"\u003e$a_1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$a_4$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, which would take \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e seconds.\u003c/p\u003e \n\u003ctable class\u003d\"sample\" summary\u003d\"sample data\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003cth\u003eSample Input 1\u003c/th\u003e \n \u003cth\u003eSample Output 1\u003c/th\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd\u003e \u003cpre\u003e5 3 0\n3 1 1 2 1\n1\n1\n3\n3\n2 3 4 5\n1 3 3 4\n4 4 5 5\n\u003c/pre\u003e \u003c/td\u003e \n \u003ctd\u003e \u003cpre\u003e3\n\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e\n\u003c/table\u003e"}}]}