{"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 \u003cp\u003eChimera Ant is an intelligent and hard-working species.\u003c/p\u003e\n \u003cp\u003eThere is a colony of Chimera Ants living in Danang, Vietnam.\n With careful infrastructure planning and hard work, they have\n built their kingdom with \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e towns, numbered from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e. The towns are connected by\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n - 1$\u003c/span\u003e two-way roads,\n such that, there is exactly one simple path between any pair of\n towns.\u003c/p\u003e\n \u003cp\u003eWinter is coming! The Chimera Ant Queen is planning to\n distribute food to the \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e\n towns: the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-th town\n will receive \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i$\u003c/span\u003e units\n of food.\u003c/p\u003e\n \u003cp\u003eHowever, the ants feel that the plan is not fair. The ants\n demand justice! They submit \u003cspan class\u003d\"tex2jax_process\"\u003e$q$\u003c/span\u003e requests. In each request,\n \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e towns \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\n from \u003cspan class\u003d\"tex2jax_process\"\u003e$\\ell $\u003c/span\u003e to\n \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\n town \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e to town\n \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e is the number of edges\n 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 ,\n p_{\\ell } \u003d v$\u003c/span\u003e denotes the simple path between town\n \u003cspan class\u003d\"tex2jax_process\"\u003e$u$\u003c/span\u003e and town \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\n denotes the simple path between town \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e and town \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e. The request says that for every\n \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, town \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ i$\u003c/span\u003e and town \u003cspan class\u003d\"tex2jax_process\"\u003e$q_ i$\u003c/span\u003e receive the same amount of\n food.\u003c/p\u003e\n \u003cp\u003eChanging the food distribution plan turns out to be a\n difficult problem. The Chimera Ant Queen has a non-negative\n integer \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e, and each\n second, she can change the plan by applying the following\n steps:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eSelect an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eSelect a town \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eEither decrease or increase the amount of food\n distributed to town \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,\n the Chimera Ant Queen can either set \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i :\u003d a_ i + (t \\cdot k + 1)$\u003c/span\u003e\n or \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i :\u003d a_ i - (t \\cdot k\n + 1)$\u003c/span\u003e. After this step, \u003cb class\u003d\"bfseries\"\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i$\u003c/span\u003e must\n be a non-negative integer\u003c/b\u003e, as we cannot distribute a\n negative amount of food.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eWhat is the shortest time it would take for the Chimera Ant\n Queen to change the food distribution plan to satisfy all the\n 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 towns, the\n number of requests and the integer the Chimera Ant Queen has\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\le n \\le 5 \\cdot 10^5, 1 \\le\n 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\n \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i$\u003c/span\u003e is the initial\n amount of food distributed to town \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\n contain \u003cspan class\u003d\"tex2jax_process\"\u003e$n - 1$\u003c/span\u003e integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$p_2, p_3, \\ldots p_ n$\u003c/span\u003e\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\leq p_ i \u0026lt; i)$\u003c/span\u003e,\n one on each line, meaning that there is a two-way road\n connecting town \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ i$\u003c/span\u003e and\n town \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\n lines contains \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e\n 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, describing one request\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\le u, v, x, y \\le\n n)$\u003c/span\u003e. It is guaranteed that the two simple paths from\n \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\u003eThe input guarantees that there is exactly one simple path\n between any pair of towns, and it is possible to satisfy all\n \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 seconds\n it would take for the Chimera Ant Queen to change the food\n distribution plan.\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 roads:\n \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 \u003cspan class\u003d\"tex2jax_process\"\u003e$k \u003d 0$\u003c/span\u003e, in each\n second, the Chimera Ant Queen can either increase or decrease\n \u003cspan class\u003d\"tex2jax_process\"\u003e$a_ i$\u003c/span\u003e\n 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 \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\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\n\u003c/body\u003e\n "}}]}