{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e 题意可以看蓝书 0x54 树形DP 里 二次扫描与换根法 这一小节的例题题意。 \u003c/div\u003e\n\u003cdiv\u003e -------------------------------------------------------------- \u003c/div\u003e\n\n\u003cdiv\u003e\u003cp\u003e树木是自然景观的重要组成部分,因为它们可以防止侵蚀,并在树叶中和树叶下提供特定的以太保护生态系统。 还发现树木在产生氧气和减少大气中的二氧化碳以及调节地面温度方面发挥着重要作用。 它们也是园林绿化和农业的重要元素,无论是因为它们的审美吸引力还是它们的果园作物(如苹果)。 来自树木的木材是一种常见的建筑材料。 \u003c/p\u003e\u003cp\u003e树木在世界上的许多神话故事中也扮演着不可或缺的角色。 许多学者对寻找树木的奇特属性很感兴趣,例如树的中心、树木计数、树木着色。 A(\u003ci\u003ex\u003c/i\u003e)就是其中一个性质。\u003c/p\u003e\u003cp\u003eA(\u003ci\u003ex\u003c/i\u003e)(节点\u003ci\u003ex\u003c/i\u003e的累积度)是 定义如下:\u003c/p\u003e\u003cp\u003e\u003c/p\u003e\u003col\u003e\u003cli\u003e树的每条边都具有正容量。\u003c/li\u003e\u003cli\u003e树中度数为1的节点称为终端 .\u003c/li\u003e\u003cli\u003e每条边的流量不能超过它的容量。\u003c/li\u003e\u003cli\u003e\u003ci\u003eA\u003c/i\u003e(\u003ci\u003ex\u003c/i\u003e)是最大流量 节点\u003ci\u003ex\u003c/i\u003e可以流向其他终端节点。\u003c/li\u003e\u003c/ol\u003e\u003cp\u003e由于定义可能比较难理解,下面举例说明:\u003c/p\u003e\u003cp\u003e \u003cimg src\u003d\"CDN_BASE_URL/68817933e8e32f44410dadbf657a6ea2?v\u003d1682164882\"\u003e\u003c/p\u003e\n\u003cbr\u003e\t\u003ctable border\u003d\"0\" width\u003d\"69%\" id\u003d\"table1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"3\"\u003eA(1)\u003d11+5+8\u003d24\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"15%\"\u003eDetails:\u003c/td\u003e\u003ctd width\u003d\"19%\"\u003e1\u003cb\u003e-\u0026gt;\u003c/b\u003e2\u003c/td\u003e\u003ctd width\u003d\"63%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"15%\"\u003e \u003c/td\u003e\u003ctd width\u003d\"19%\"\u003e1\u003cb\u003e-\u0026gt;\u003c/b\u003e4\u003cb\u003e-\u0026gt;\u003c/b\u003e3\u003c/td\u003e\u003ctd width\u003d\"63%\"\u003e5\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"15%\"\u003e \u003c/td\u003e\u003ctd width\u003d\"19%\"\u003e1\u003cb\u003e-\u0026gt;\u003c/b\u003e4\u003cb\u003e-\u0026gt;\u003c/b\u003e5\u003c/td\u003e\u003ctd width\u003d\"63%\"\u003e8(since 1\u003cb\u003e-\u0026gt;\u003c/b\u003e4 has capacity of 13)\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"97%\" colspan\u003d\"3\"\u003eA(2)\u003d5+6\u003d11\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"15%\"\u003eDetails:\u003c/td\u003e\u003ctd width\u003d\"19%\"\u003e2\u003cb\u003e-\u0026gt;\u003c/b\u003e1\u003cb\u003e-\u0026gt;\u003c/b\u003e4\u003cb\u003e-\u0026gt;\u003c/b\u003e3\u003c/td\u003e\u003ctd width\u003d\"63%\"\u003e5\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"15%\"\u003e \u003c/td\u003e\u003ctd width\u003d\"19%\"\u003e2\u003cb\u003e-\u0026gt;\u003c/b\u003e1\u003cb\u003e-\u0026gt;\u003c/b\u003e4\u003cb\u003e-\u0026gt;\u003c/b\u003e5\u003c/td\u003e\u003ctd width\u003d\"63%\"\u003e6\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"97%\" colspan\u003d\"3\"\u003eA(3)\u003d5\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"15%\"\u003eDetails: \u003c/td\u003e\u003ctd width\u003d\"19%\"\u003e3\u003cb\u003e-\u0026gt;\u003c/b\u003e4\u003cb\u003e-\u0026gt;\u003c/b\u003e5\u003c/td\u003e\u003ctd width\u003d\"63%\"\u003e5\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"97%\" colspan\u003d\"3\"\u003eA(4)\u003d11+5+10\u003d26\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"15%\"\u003eDetails:\u003c/td\u003e\u003ctd width\u003d\"19%\"\u003e4\u003cb\u003e-\u0026gt;\u003c/b\u003e1\u003cb\u003e-\u0026gt;\u003c/b\u003e2\u003c/td\u003e\u003ctd width\u003d\"63%\"\u003e11\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"15%\"\u003e \u003c/td\u003e\u003ctd width\u003d\"19%\"\u003e4\u003cb\u003e-\u0026gt;\u003c/b\u003e3\u003c/td\u003e\u003ctd width\u003d\"63%\"\u003e5\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"15%\"\u003e \u003c/td\u003e\u003ctd width\u003d\"19%\"\u003e4\u003cb\u003e-\u0026gt;\u003c/b\u003e5\u003c/td\u003e\u003ctd width\u003d\"63%\"\u003e10\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"97%\" colspan\u003d\"3\"\u003eA(5)\u003d10\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"15%\"\u003eDetails:\u003c/td\u003e\u003ctd width\u003d\"19%\"\u003e5\u003cb\u003e-\u0026gt;\u003c/b\u003e4\u003cb\u003e-\u0026gt;\u003c/b\u003e1\u003cb\u003e-\u0026gt;\u003c/b\u003e2\u003c/td\u003e\u003ctd width\u003d\"63%\"\u003e10\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003cp\u003e一棵树的堆积度是其节点之间的最大堆积度。 在这里你的任务是找到给定树的堆积度。\u003c/p\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行是一个整数\u003ci\u003eT\u003c/i\u003e,表示测试用例的个数。 每个测试用例的第一行是一个正整数\u003ci\u003en\u003c/i\u003e。 下面每行\u003ci\u003en\u003c/i\u003e - 1行包含三个整数\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e, \u003ci\u003ez\u003c/i\u003e,中间用空格隔开,代表那里 是节点\u003ci\u003ex\u003c/i\u003e和节点\u003ci\u003ey\u003c/i\u003e之间的边,边的容量为\u003ci\u003ez\u003c/i\u003e。 节点编号从1到\u003ci\u003en\u003c/i\u003e。\u003cbr\u003e所有元素都是不超过200000的非负整数。你可以假设测试数据都是树指标。\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e对于每个测试用例,在一行中输出结果。 \u003cbr\u003e\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e1\n5\n1 2 11\n1 4 13\n3 4 5\n4 5 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e26\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}