{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\n\u003ch1\u003e\u003c/h1\u003e\n\u003cp\u003e图 \u003ci\u003eG\u003c/i\u003e \u003d (\u003ci\u003eV\u003c/i\u003e, \u003ci\u003eE\u003c/i\u003e) 是一种数据结构,其中 \u003ci\u003eV\u003c/i\u003e 是顶点的有限集合,\u003ci\u003eE\u003c/i\u003e 是由边集表示的 \u003ci\u003eV\u003c/i\u003e 上的二元关系。图 1 展示了一个图(或多个图)的例子。\u003c/p\u003e\n\u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/7706a14f3c85b1d6c9f1a22b918b3873?v\u003d1699010549\"\u003e\n \u003cbr\u003e\u003cb\u003e图 1\u003c/b\u003e\n\u003c/center\u003e\n\u003cp\u003e自由树是一个连通的、无环的、无向图。有根树是一种自由树,其中一个顶点与其他顶点有所区别。有根树的一个顶点被称为“节点”。\u003c/p\u003e\n\u003cp\u003e你的任务是编写一个程序,为给定的有根树 \u003ci\u003eT\u003c/i\u003e 的每个节点 \u003ci\u003eu\u003c/i\u003e 报告以下信息:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003e节点 \u003ci\u003eu\u003c/i\u003e 的 ID\u003c/li\u003e\n \u003cli\u003e节点 \u003ci\u003eu\u003c/i\u003e 的父节点\u003c/li\u003e\n \u003cli\u003e节点 \u003ci\u003eu\u003c/i\u003e 的深度\u003c/li\u003e\n \u003cli\u003e节点类型(根节点、内部节点或叶节点)\u003c/li\u003e\n \u003cli\u003e节点 \u003ci\u003eu\u003c/i\u003e 的子节点列表\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e如果从树 \u003ci\u003eT\u003c/i\u003e 的根 \u003ci\u003er\u003c/i\u003e 到节点 \u003ci\u003ex\u003c/i\u003e 的路径上的最后一条边是 (\u003ci\u003ep\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e),那么 \u003ci\u003ep\u003c/i\u003e 就是 \u003ci\u003ex\u003c/i\u003e 的\u003cb\u003e父节点\u003c/b\u003e,而 \u003ci\u003ex\u003c/i\u003e 是 \u003ci\u003ep\u003c/i\u003e 的\u003cb\u003e子节点\u003c/b\u003e。根节点是 \u003ci\u003eT\u003c/i\u003e 中唯一没有父节点的节点。\u003c/p\u003e\u003c!--\n\u003cp\u003e\n如果两个节点有同一个父节点,他们就是\u003cb\u003e兄弟节点\u003c/b\u003e。\n\u003c/p\u003e\n--\u003e\n\u003cp\u003e没有子节点的节点是\u003cb\u003e外部节点\u003c/b\u003e或\u003cb\u003e叶节点\u003c/b\u003e。非叶节点是\u003cb\u003e内部节点\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e有根树 \u003ci\u003eT\u003c/i\u003e 中节点 \u003ci\u003ex\u003c/i\u003e 的子节点数量被称为 \u003ci\u003ex\u003c/i\u003e 的\u003cb\u003e度\u003c/b\u003e。\u003c/p\u003e\n\u003cp\u003e从根 \u003ci\u003er\u003c/i\u003e 到节点 \u003ci\u003ex\u003c/i\u003e 的路径长度是 \u003ci\u003ex\u003c/i\u003e 在 \u003ci\u003eT\u003c/i\u003e 中的\u003cb\u003e深度\u003c/b\u003e。\u003c/p\u003e\n\u003cp\u003e这里,给定的树由 \u003ci\u003en\u003c/i\u003e 个节点组成,每个节点都有一个从 0 到 \u003ci\u003en\u003c/i\u003e-1 的唯一 ID。\u003c/p\u003e\n\u003cp\u003e图 2 显示了一个有根树的例子,其中每个节点的 ID 由圆圈中的数字表示(节点)。这个例子对应于第一个样本输入。\u003c/p\u003e\n\u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/361a9b0092cdfee172eecacd7ce907f6?v\u003d1699010549\"\u003e\n \u003cbr\u003e\u003cb\u003e图 2\u003c/b\u003e\n\u003c/center\u003e\n\u003ch2\u003e输入\u003c/h2\u003e\n\u003cp\u003e输入的第一行包含一个整数 \u003ci\u003en\u003c/i\u003e,表示树的节点数量。\u003c/p\u003e\n\u003cp\u003e在接下来的 \u003ci\u003en\u003c/i\u003e 行中,每个节点 \u003ci\u003eu\u003c/i\u003e 的信息以以下格式给出:\u003c/p\u003e\n\u003cp\u003e\u003ci\u003eid\u003c/i\u003e \u003ci\u003ek\u003c/i\u003e \u003ci\u003ec\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003ci\u003ec\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e ... \u003ci\u003ec\u003csub\u003ek\u003c/sub\u003e\u003c/i\u003e\u003c/p\u003e\n\u003cp\u003e其中 \u003ci\u003eid\u003c/i\u003e 是节点 \u003ci\u003eu\u003c/i\u003e 的 ID,\u003ci\u003ek\u003c/i\u003e 是节点 \u003ci\u003eu\u003c/i\u003e 的度,\u003ci\u003ec\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e ... \u003ci\u003ec\u003csub\u003ek\u003c/sub\u003e\u003c/i\u003e 是节点 \u003ci\u003eu\u003c/i\u003e 的第 1,... \u003ci\u003ek\u003c/i\u003e 个子节点的 ID。如果节点没有子节点,\u003ci\u003ek\u003c/i\u003e 就是 0。\u003c/p\u003e\n\u003ch2\u003e输出\u003c/h2\u003e\n\u003cp\u003e按 ID 顺序打印每个节点的信息,格式如下:\u003c/p\u003e\n\u003cp\u003e\u003cspan\u003e节点\u003c/span\u003e \u003ci\u003eid\u003c/i\u003e\u003cspan\u003e: \u003c/span\u003e\u003cspan\u003e父节点 \u003d \u003c/span\u003e\u003ci\u003ep\u003c/i\u003e\u003cspan\u003e, 深度 \u003d \u003c/span\u003e\u003ci\u003ed\u003c/i\u003e\u003cspan\u003e, \u003ci\u003e类型\u003c/i\u003e\u003cspan\u003e, [\u003c/span\u003e\u003ci\u003ec\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e...\u003ci\u003ec\u003csub\u003ek\u003c/sub\u003e\u003c/i\u003e\u003cspan\u003e]\u003c/span\u003e \u003c/span\u003e\u003c/p\u003e\n\u003cp\u003e\u003ci\u003ep\u003c/i\u003e 是其父节点的 ID。如果节点没有父节点,打印 \u003cspna\u003e\n -1。\n \u003c/spna\u003e\u003c/p\u003e\n\u003cp\u003e\u003ci\u003ed\u003c/i\u003e 是节点的深度。\u003c/p\u003e\n\u003cp\u003e\u003ci\u003e类型\u003c/i\u003e 是由字符串表示的节点类型(\u003cspan\u003e根节点\u003c/span\u003e,\u003cspan\u003e内部节点\u003c/span\u003e 或 \u003cspan\u003e叶节点\u003c/span\u003e)。如果根节点可以被视为叶节点或内部节点,打印 \u003cspan\u003e根节点\u003c/span\u003e。\u003c/p\u003e\n\u003cp\u003e\u003ci\u003ec\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e...\u003ci\u003ec\u003csub\u003ek\u003c/sub\u003e\u003c/i\u003e 是作为有序树的子节点列表。\u003c/p\u003e\n\u003cp\u003e请按照下面的样本输出的格式进行打印。\u003c/p\u003e\n\u003ch2\u003e约束条件\u003c/h2\u003e\n\u003cul\u003e\n \u003cli\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100000\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch2\u003e样例输入 1\u003c/h2\u003e\n\u003cpre\u003e13\n0 3 1 4 10\n1 2 2 3\n2 0\n3 0\n4 3 5 6 7\n5 0\n6 0\n7 2 8 9\n8 0\n9 0\n10 2 11 12\n11 0\n12 0\n\u003c/pre\u003e\n\u003ch2\u003e样例输出 1\u003c/h2\u003e\n\u003cpre\u003enode 0: parent \u003d -1, depth \u003d 0, root, [1, 4, 10]\nnode 1: parent \u003d 0, depth \u003d 1, internal node, [2, 3]\nnode 2: parent \u003d 1, depth \u003d 2, leaf, []\nnode 3: parent \u003d 1, depth \u003d 2, leaf, []\nnode 4: parent \u003d 0, depth \u003d 1, internal node, [5, 6, 7]\nnode 5: parent \u003d 4, depth \u003d 2, leaf, []\nnode 6: parent \u003d 4, depth \u003d 2, leaf, []\nnode 7: parent \u003d 4, depth \u003d 2, internal node, [8, 9]\nnode 8: parent \u003d 7, depth \u003d 3, leaf, []\nnode 9: parent \u003d 7, depth \u003d 3, leaf, []\nnode 10: parent \u003d 0, depth \u003d 1, internal node, [11, 12]\nnode 11: parent \u003d 10, depth \u003d 2, leaf, []\nnode 12: parent \u003d 10, depth \u003d 2, leaf, []\n\u003c/pre\u003e\n\u003ch2\u003e样例输入 2\u003c/h2\u003e\n\u003cpre\u003e4\n1 3 3 2 0\n0 0\n3 0\n2 0\n\u003c/pre\u003e\n\u003ch2\u003e样例输出 2\u003c/h2\u003e\n\u003cpre\u003enode 0: parent \u003d 1, depth \u003d 1, leaf, []\nnode 1: parent \u003d -1, depth \u003d 0, root, [3, 2, 0]\nnode 2: parent \u003d 1, depth \u003d 1, leaf, []\nnode 3: parent \u003d 1, depth \u003d 1, leaf, []\n\u003c/pre\u003e\n\u003ch2\u003e注意\u003c/h2\u003e\n\u003cp\u003e你可以使用\u003cb\u003e左孩子,右兄弟表示法\u003c/b\u003e来实现具有以下数据的树:\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003e节点 \u003ci\u003eu\u003c/i\u003e 的父节点\u003c/li\u003e\n \u003cli\u003e节点 \u003ci\u003eu\u003c/i\u003e 的最左边的子节点\u003c/li\u003e\n \u003cli\u003e节点 \u003ci\u003eu\u003c/i\u003e 的直接右兄弟节点\u003c/li\u003e\n\u003c/ul\u003e\u003c!--\n\u003cp\u003e\n\u003ca href\u003d\"template/ALDS1_7_A_template.c\"\u003eC语言模板\u003c/a\u003e\n\u003c/p\u003e\n--\u003e\n\u003ch2\u003e参考资料\u003c/h2\u003e\n\u003cp\u003e《算法导论》,作者:Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 和 Clifford Stein。出版社:麻省理工学院出版社。\u003c/p\u003e"}}]}