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 68 69 70 71 72
| #include <cstdio> #include <map> using namespace std;
const int maxn = 10010; int n, num, time, numtime, dmax = -1, cntmax = -1;
struct node { int data, depth; node *lchild, *mchild, *rchild; };
map<int, node*> m;
node* newnode(int x) { if(x == -1) { return NULL; } node* root = new node; root->data = x; root->lchild = NULL; root->mchild = NULL; root->rchild = NULL; return root; }
void preOrder(node* root, int d) { if(root == NULL) { return; } root->depth = d; time++; int cnt = 0; if(root->lchild != NULL) cnt++; if(root->mchild != NULL) cnt++; if(root->rchild != NULL) cnt++; if(cnt >= cntmax && d > dmax) { dmax = d; cntmax = cnt; num = root->data; numtime = time; } preOrder(root->lchild, d + 1); preOrder(root->mchild, d + 1); preOrder(root->rchild, d + 1); }
int main() { scanf("%d", &n); int n1, n2, n3, n4; node* root; for(int i = 0; i < n; i++) { scanf("%d %d %d %d", &n1, &n2, &n3, &n4); if(i == 0) { root = newnode(n1); m[n1] = root; } node* rtemp = m[n1]; rtemp->lchild = newnode(n2); rtemp->mchild = newnode(n3); rtemp->rchild = newnode(n4); m[n2] = rtemp->lchild; m[n3] = rtemp->mchild; m[n4] = rtemp->rchild; } preOrder(root, 1); printf("%d %d\n", num, numtime); return 0; }
|