{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e .sampledata { font-family: \"Courier New\", Courier, monospace; white-space: pre; }\u003c/style\u003e\u003cdiv\u003e\n 烟花表演是最引人注目的节日活动之一。在表演中,所有的烟花必须同时爆炸。为了确保安\n\u003c/div\u003e \n\u003cdiv\u003e\n 全,烟花被安置在远离开关的位置上,通过一些导火索与开关相连。导火索的连接方式形成\n\u003c/div\u003e \n\u003cdiv\u003e\n 一棵树,烟花是树叶,如[图1]所示。火花从开关出发,沿导火索移动。每当火花抵达一个分\n\u003c/div\u003e \n\u003cdiv\u003e\n 叉点时,它会扩散到与之相连的所有导火索,继续燃烧。导火索燃烧的速度是一个固定常\n\u003c/div\u003e \n\u003cdiv\u003e\n 数。[图1]展示了六枚烟花{E1,E2...E6 }的连线布局,以及每根导火索的长度。图中还标\n\u003c/div\u003e \n\u003cdiv\u003e\n 注了当在时刻 从开关点燃火花时,每一发烟花的爆炸时间。\n\u003c/div\u003e \n\u003cdiv\u003e\n \u003cimg SRC\u003d\"CDN_BASE_URL/1f27fb614eaff55ae97d767bd4831151?v\u003d1591682635\" width\u003d\"301\" height\u003d\"306\" alt\u003d\"\"\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n Hyunmin为烟花表演设计了导火索的连线布局。不幸的是,在他设计的布局中,烟花不一定\n\u003c/div\u003e \n\u003cdiv\u003e\n 同时爆炸。我们希望修改一些导火索的长度,让所有烟花在同一时刻爆炸。例如,为了让[图\n\u003c/div\u003e \n\u003cdiv\u003e\n 1]中的所有烟花在时刻 13爆炸,我们可以像[图2]中左边那样调整导火索长度。类似地,为\n\u003c/div\u003e \n\u003cdiv\u003e\n 了让[图1]中的所有烟花在时刻 14爆炸,我们可以像[图2]中右边那样调整长度。\n\u003c/div\u003e \n\u003cdiv\u003e\n \u003cimg SRC\u003d\"CDN_BASE_URL/69172391f63a2cc9036ec9e1743dda08?v\u003d1591682635\" width\u003d\"584\" height\u003d\"349\" alt\u003d\"\"\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n 修改导火索长度的代价等于修改前后长度之差的绝对值。例如,将[图1]中布局修改为[图2]\n\u003c/div\u003e \n\u003cdiv\u003e\n 左边布局的总代价为6 ,而将[图1]中布局修改为[图2]右边布局的总代价为 5.\n\u003c/div\u003e \n\u003cdiv\u003e\n 导火索的长度可以被减为0 ,同时保持连通性不变。\n\u003c/div\u003e \n\u003cdiv\u003e\n 给定一个导火索的连线布局,你需要编写一个程序,去调整导火索长度,让所有的烟花在同\n\u003c/div\u003e \n\u003cdiv\u003e\n 一时刻爆炸,并使得代价最小。\n\u003c/div\u003e \n\u003cdiv\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\u0026nbsp;所有的输入均为正整数。令 N代表分叉点的数量, M代表烟花的数量。分叉点从1 到N 编\u003c/p\u003e \n\u003cdiv\u003e\n 号,编号为1 的分叉点是开关。烟花从N+1 到 N+M编号。1\u0026lt;\u003dN+M\u0026lt;\u003d300,000\n\u003c/div\u003e \n\u003cdiv\u003e\n 输入格式如下:\n\u003c/div\u003e \n\u003cdiv\u003e\n N M\n\u003c/div\u003e \n\u003cdiv\u003e\n P\n \u003csub\u003e2\u003c/sub\u003e C\n \u003csub\u003e2\u003c/sub\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n P\n \u003csub\u003e3\u003c/sub\u003e C\n \u003csub\u003e3\u003c/sub\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n ...\n\u003c/div\u003e \n\u003cdiv\u003e\n P\n \u003csub\u003en\u003c/sub\u003e C\n \u003csub\u003en\u003c/sub\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n P\n \u003csub\u003eN+1\u003c/sub\u003e C\n \u003csub\u003eN+1\u003c/sub\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n ...\n\u003c/div\u003e \n\u003cdiv\u003e\n P\n \u003csub\u003eN+m\u003c/sub\u003e C\n \u003csub\u003eN+M\u003c/sub\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n 其中Pi 满足 1\u0026lt;\u003dPi\u0026lt;i,代表和分叉点或烟花i 相连的分叉点。 Ci代表连接它们的导火索长\n\u003c/div\u003e \n\u003cdiv\u003e\n 度( 1\u0026lt;\u003dCi\u0026lt;\u003d10^9)。除开关外,每个分叉点和多于1 条导火索相连,而每发烟花恰好与 1条导\n\u003c/div\u003e \n\u003cdiv\u003e\n 火索相连。\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\u0026nbsp;输出调整导火索长度,让所有烟花同时爆炸,所需要的最小代价\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e4 6\r\n1 5\r\n2 5\r\n2 8\r\n3 3\r\n3 2\r\n3 3\r\n2 9\r\n4 4\r\n4 3\u003c/span\u003e\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e5\u003c/span\u003e\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\u003c/p\u003e"}}]}