aoj 二分探索

ALDS1_7_A Tree - Rooted Trees

ALDS1_7_A Tree - Rooted Trees
Feb. 2, 2020, 1:52 p.m.

解答

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 #define MAX 100001 #define NIL -1 struct Node { int parent, left, right; }; void print(int i, Node arr[], int ds[]) { cout << "node " << i << ": "; cout << "parent = " << arr[i].parent; cout << ", depth = " << ds[i]; cout << ", "; if (arr[i].parent == NIL) cout << "root"; else if (arr[i].left == NIL) cout << "leaf"; else cout << "internal node"; cout << ", ["; if (arr[i].left != NIL) { int current = arr[i].left; cout << current; while (arr[current].right != NIL) { current = arr[current].right; cout << ", " << current; } } cout << "]" << endl; } void depth(int n, int d, Node nodes[], int ds[]) { ds[n] = d; if (nodes[n].right != NIL) depth(nodes[n].right, d, nodes, ds); if (nodes[n].left != NIL) depth(nodes[n].left, d+1, nodes, ds); } int main() { int n, id, k, c, root; Node T[MAX]; int D[MAX]; cin >> n; for (int i=0; i> id >> k; int left; for (int j = 0; j < k; j++) { cin >> c; if (j == 0) T[id].left = c; else T[left].right = c; T[c].parent = id; left = c; } } for (int i=0; i