{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\n\n\n\u003cp\u003e\nA graph \u003ci\u003eG\u003c/i\u003e \u003d (\u003ci\u003eV\u003c/i\u003e, \u003ci\u003eE\u003c/i\u003e) is a data structure where \u003ci\u003eV\u003c/i\u003e is a finite set of vertices and \u003ci\u003eE\u003c/i\u003e is a binary relation on \u003ci\u003eV\u003c/i\u003e represented by a set of edges. Fig. 1 illustrates an example of a graph (or graphs).\n\u003c/p\u003e\n\n\u003ccenter\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/7706a14f3c85b1d6c9f1a22b918b3873?v\u003d1715807704\"\u003e\u003cbr\u003e\n\u003cb\u003eFig. 1\u003c/b\u003e\n\u003c/center\u003e\n\n\u003cp\u003e\nA free tree is a connnected, acyclic, undirected graph. A rooted tree is a free tree in which one of the vertices is distinguished from the others. A vertex of a rooted tree is called \"node.\"\n\u003c/p\u003e\n\n\n\u003cp\u003e\nYour task is to write a program which reports the following information for each node \u003ci\u003eu\u003c/i\u003e of a given rooted tree \u003ci\u003eT\u003c/i\u003e:\n\u003c/p\u003e\n\n\u003cul\u003e\n\u003cli\u003enode ID of \u003ci\u003eu\u003c/i\u003e\u003c/li\u003e\n\u003cli\u003eparent of \u003ci\u003eu\u003c/i\u003e\u003c/li\u003e\n\u003cli\u003edepth of \u003ci\u003eu\u003c/i\u003e\u003c/li\u003e\n\u003cli\u003enode type (root, internal node or leaf)\u003c/li\u003e\n\u003cli\u003ea list of chidlren of \u003ci\u003eu\u003c/i\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\n\n\u003cp\u003e\nIf the last edge on the path from the root \u003ci\u003er\u003c/i\u003e of a tree \u003ci\u003eT\u003c/i\u003e to a node \u003ci\u003ex\u003c/i\u003e is (\u003ci\u003ep\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e), then \u003ci\u003ep\u003c/i\u003e is the \u003cb\u003eparent\u003c/b\u003e of \u003ci\u003ex\u003c/i\u003e, and \u003ci\u003ex\u003c/i\u003e is a \u003cb\u003echild\u003c/b\u003e of \u003ci\u003ep\u003c/i\u003e. The root is the only node in \u003ci\u003eT\u003c/i\u003e with no parent.\n\u003c/p\u003e\n\n\u003c!--\n\u003cp\u003e\nIf two nodes have the same parent, they are \u003cb\u003esiblings\u003c/b\u003e.\n\u003c/p\u003e\n--\u003e\n\n\u003cp\u003e\nA node with no children is an \u003cb\u003eexternal node\u003c/b\u003e or \u003cb\u003eleaf\u003c/b\u003e. A nonleaf node is an \u003cb\u003einternal node\u003c/b\u003e\n\u003c/p\u003e\n\n\u003cp\u003e\nThe number of children of a node \u003ci\u003ex\u003c/i\u003e in a rooted tree \u003ci\u003eT\u003c/i\u003e is called the \u003cb\u003edegree\u003c/b\u003e of \u003ci\u003ex\u003c/i\u003e.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe length of the path from the root \u003ci\u003er\u003c/i\u003e to a node \u003ci\u003ex\u003c/i\u003e is the \u003cb\u003edepth\u003c/b\u003e of \u003ci\u003ex\u003c/i\u003e in \u003ci\u003eT\u003c/i\u003e.\n\u003c/p\u003e\n\n\n\n\u003cp\u003e\nHere, the given tree consists of \u003ci\u003en\u003c/i\u003e nodes and evey node has a unique ID from 0 to \u003ci\u003en\u003c/i\u003e-1.\n\u003c/p\u003e\n\n\u003cp\u003e\nFig. 2 shows an example of rooted trees where ID of each node is indicated by a number in a circle (node). The example corresponds to the first sample input.\n\u003c/p\u003e\n\n\u003ccenter\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/361a9b0092cdfee172eecacd7ce907f6?v\u003d1715807704\"\u003e\u003cbr\u003e\n\u003cb\u003eFig. 2\u003c/b\u003e\n\u003c/center\u003e\n\n\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003e\nThe first line of the input includes an integer \u003ci\u003en\u003c/i\u003e, the number of nodes of the tree.\n\u003c/p\u003e\n\u003cp\u003e\nIn the next \u003ci\u003en\u003c/i\u003e lines, the information of each node \u003ci\u003eu\u003c/i\u003e is given in the following format:\n\u003c/p\u003e\n\n\u003cp\u003e\n\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\n\u003c/p\u003e\n\n\u003cp\u003e\nwhere \u003ci\u003eid\u003c/i\u003e is the node ID of \u003ci\u003eu\u003c/i\u003e, \u003ci\u003ek\u003c/i\u003e is the degree of \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 are node IDs of 1st, ... \u003ci\u003ek\u003c/i\u003eth child of \u003ci\u003eu\u003c/i\u003e. If the node does not have a child, the \u003ci\u003ek\u003c/i\u003e is 0.\n\u003c/p\u003e\n\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nPrint the information of each node in the following format ordered by IDs:\n\u003c/p\u003e\n\n\u003cp\u003e\n\u003cspan\u003enode\u003c/span\u003e \u003ci\u003eid\u003c/i\u003e\u003cspan\u003e: \u003c/span\u003e\u003cspan\u003eparent \u003d \u003c/span\u003e\u003ci\u003ep\u003c/i\u003e\u003cspan\u003e, depth \u003d \u003c/span\u003e\u003ci\u003ed\u003c/i\u003e\u003cspan\u003e, \u003ci\u003etype\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\n\u003c/span\u003e\u003c/p\u003e\n\n\u003cp\u003e\n\u003ci\u003ep\u003c/i\u003e is ID of its parent. If the node does not have a parent, print \u003cspna\u003e-1.\n\u003c/spna\u003e\u003c/p\u003e\n\u003cp\u003e\n\u003ci\u003ed\u003c/i\u003e is depth of the node.\n\u003c/p\u003e\n\n\u003cp\u003e\n\u003ci\u003etype\u003c/i\u003e is a type of nodes represented by a string (\u003cspan\u003eroot\u003c/span\u003e, \u003cspan\u003einternal node\u003c/span\u003e or \u003cspan\u003eleaf\u003c/span\u003e). If the root can be considered as a leaf or an internal node, print \u003cspan\u003eroot\u003c/span\u003e.\n\u003c/p\u003e\n\n\u003cp\u003e\n\u003ci\u003ec\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e...\u003ci\u003ec\u003csub\u003ek\u003c/sub\u003e\u003c/i\u003e is the list of children as a ordered tree.\n\u003c/p\u003e\n\n\n\u003cp\u003e\nPlease follow the format presented in a sample output below.\n\u003c/p\u003e\n\n\n\u003ch2\u003eConstraints\u003c/h2\u003e\n\n\u003cul\u003e\n\u003cli\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100000\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch2\u003eSample Input 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\u003eSample Output 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\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\u003cpre\u003e4\n1 3 3 2 0\n0 0\n3 0\n2 0\n\u003c/pre\u003e\n\u003ch2\u003eSample Output 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\n\u003ch2\u003eNote\u003c/h2\u003e\n\u003cp\u003e\nYou can use a \u003cb\u003eleft-child, right-sibling representation\u003c/b\u003e to implement a tree which has the following data:\n\u003c/p\u003e\n\n\u003cul\u003e\n\u003cli\u003ethe parent of \u003ci\u003eu\u003c/i\u003e\u003c/li\u003e\n\u003cli\u003ethe leftmost child of \u003ci\u003eu\u003c/i\u003e\u003c/li\u003e\n\u003cli\u003ethe immediate right sibling of \u003ci\u003eu\u003c/i\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003c!--\n\u003cp\u003e\n\u003ca href\u003d\"template/ALDS1_7_A_template.c\"\u003eTemplate in C\u003c/a\u003e\n\u003c/p\u003e\n--\u003e\n\n\u003ch2\u003eReference\u003c/h2\u003e\n\n\u003cp\u003e\nIntroduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.\n\u003c/p\u003e\n\n\n"}}]}