Binary tree (Beijing University of Posts and Telecommunications machine test questions) (day85)

1： subject

 Given a  n  Nodes （ Number  1∼n） A binary tree , Its root node is  1  Number point .

 Conduct  m  Time to ask , Ask the shortest path length between two nodes each time .

 All sides of the tree are  1.

 Input format 
 The first line contains an integer  T, Expressing common ownership  T  Group test data .

 The first row of each set of data contains two integers  n,m.

 Next  n  That's ok , Each line contains two integers , Among them the first  i  The integer of the row represents the node  i  Child node number of . If there is no child node, output  −1.

 Next  m  That's ok , Each line contains two integers , Indicates the number of the two nodes to be queried .

 Output format 
 Output of each group of test data  m  That's ok , Represents the shortest path length between two nodes of the query .

 Data range 
1≤T≤10,
1≤n,m≤1000
 sample input ：
1
8 4
2 3
4 5
6 -1
-1 -1
-1 7
-1 -1
8 -1
-1 -1
1 6
4 6
4 5
8 1
 sample output ：
2
4
2
4


 difficulty ： Simple 
 when / Empty limit ：1s / 64MB
 Total number of passes ：654
 Total attempts ：1453
 source ： Beijing University of Posts and Telecommunications postgraduate entrance examination questions 
 Algorithm tags 

2： Code implementation

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int l[N], r[N], p[N];
int dist[N];

void dfs(int u, int d)
{
    
    dist[u] = d;
    if (l[u] != -1) dfs(l[u], d + 1);
    if (r[u] != -1) dfs(r[u], d + 1);
}

int get_lca(int a, int b)
{
    
    if (dist[a] < dist[b]) return get_lca(b, a);
    while (dist[a] > dist[b]) a = p[a];
    while (a != b) a = p[a], b = p[b];
    return a;
}

int main()
{
    
    int T;
    cin >> T;
    while (T -- )
    {
    
        cin >> n >> m;
        for (int i = 1; i <= n; i ++ )
        {
    
            int a, b;
            cin >> a >> b;
            l[i] = a, r[i] = b;
            if (a != -1) p[a] = i;
            if (b != -1) p[b] = i;
        }

        dfs(1, 0);

        while (m -- )
        {
    
            int a, b;
            cin >> a >> b;
            int c = get_lca(a, b);
            cout << dist[a] + dist[b] - dist[c] * 2 << endl;
        }

    }

    return 0;
}