BUAA magpie nesting

【 Problem description 】

Magpies usually choose a tree with the highest branches （ That is, the node with the highest height among the nodes with the most branches ） Nest in a place （ The structure is the most stable ）. Given a trident tree , Calculate the location where magpies build their nests （ There may be more than one , When there are multiple nodes, the corresponding node information should be given in the order of traversing the tree , Including the node number and the number of accesses to the node in the previous order ）. For example, the following figure is a trident tree ：

The node in the tree has at most three branches , The highest node with three branches is 23 Number and 15 Node No , According to the previous order, the traversal order will be 19 Accessed to 23 Node No , The first 31 Accessed to 15 Node No .

requirement ： When traversing the branches of the Trident tree according to the previous order, you should first access the left branch , Then visit the middle branch , Finally, visit the right branch ; The root node is 1 Access nodes , And there are at most 100 Nodes .

【 Input form 】

First, input an integer from the console to represent the number of entries in the tree node relationship , Then start on the next line , Enter the relationship between tree nodes from the root . The node number is from number 1 Start , Such as 1 Represents the root node of the tree , The number of other nodes is greater than 1, No repetition , But the numbering is irregular . The relationship between nodes in the tree is described in the following way ：

R S1 S2 S3

among R Is the bifurcation node ,S1,S2,S3 They are tree forks R Left of 、 in 、 Right child node , Because it is a trident tree ,S1,S2,S3 At most 2 Item is empty , Used when this item is empty 0 Express . Each item is separated by a space , Finally, there is a carriage return . Such as ：

1 5 6 0

Indicate number 1 The root of the tree has two forks , The numbers are 5 and 6.

Be careful ： The input order of node relationship is to input the relationship between root and child nodes from the root node in turn , Then enter the relationship between the bifurcation node and the child node , When entering a node relationship , Its parent node must already exist , But not necessarily according to the level of input .

【 Output form 】

Output the node information with the highest height among the nodes with the most branches according to the previous traversal order , Each node information occupies one line , It includes the node number and the number of accesses to the node in the previous order , Separate data with a space .

【 The sample input 】

18

1 2 3 4

4 5 0 0

3 6 7 8

2 9 10 0

7 21 22 0

21 23 24 0

23 25 26 27

9 28 29 0

28 30 31 37

30 32 0 0

31 33 36 0

33 34 35 0

5 11 12 13

11 14 0 0

12 15 0 0

13 16 0 0

15 17 18 19

19 20 0 0

【 Sample output 】

23 19

15 31

【 Sample explanation 】

Input 18 Tree node relationship , The trigeminal tree established according to these relationships is shown in the above figure . The node in the tree has at most three branches , The highest node with three branches is 23 Number and 15 Node No , According to the previous order, the traversal order will be 19 Accessed to 23 Node No , The first 31 Accessed to 15 Node No . The root node is 1 Visited nodes .

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 102
struct triple_tree
{
    
    int num;
    struct triple_tree *child[3];
};
typedef struct queue
{
    
    int num, when, level, point;
} queue;

typedef struct triple_tree tree;
queue result[MAXSIZE];
tree nodes[MAXSIZE];
int n, i, cup[3], head, j;
int count;

void tree_vt(tree *root, int level)
{
    
    result[count].level = level;
    result[count].num = root->num;
    result[count].when = count + 1;
    result[count].point = 0;
    for (i = 0; i < 3; i++)
    {
    
        if (root->child[i] != NULL)
        {
    
            result[count].point += 1;
        }
    }
    count++;
    return;
}

void fvisit(tree *root, int level)
{
    
    int i;
    tree_vt(root, level);
    for (i = 0; i < 3; i++)
    {
    
        if (root->child[i] != NULL)
        {
    
            fvisit(root->child[i], level + 1);
        }
    }
    return;
}

int cmp(queue *a, queue *b)
{
    
    if (a->point > b->point)
        return -1;
    else if (a->point == b->point && a->level > b->level)
        return -1;
    else if (a->point == b->point && a->level == b->level && a->when < b->when)
        return -1;
    return 1;
}

int main()
{
    
    scanf("%d", &n);
    while (n--)
    {
    
        scanf("%d%d%d%d", &head, &cup[0], &cup[1], &cup[2]);
        for (i = 0; i < 3; i++)
        {
    
            if (cup[i] != 0)
                nodes[head - 1].child[i] = &nodes[cup[i] - 1];
            else
                nodes[head - 1].child[i] = NULL;
        }
    }
    for (i = 0; i < MAXSIZE; i++)
        nodes[i].num = i + 1;
    fvisit(&nodes[0], 1);
    qsort(&result[0], count + 1, sizeof(queue), (const void *)cmp);
    i = 0;
    n = result[0].level;
    while (result[i].level == n)
    {
    
        printf("%d %d\n", result[i].num, result[i].when);
        i++;
    }
    return 0;
}

BUAAer？