题目描述

Zeoy 最喜欢说一句话”我是你爹”。由此在实验室引发了一波认儿子狂潮。
现在，给定 n 个父子关系，以及一对询问，求 x 和 y 两个人间隔的辈份。
如果 x 是 y 的父亲，那么两人的辈分间隔为 1 ；
如果 x 是 y 的父亲的父亲，那么两人的辈分间隔为 2 ；
…… 以此类推。

输入格式

每个测试文件有 T 组测试样例。
第一行输入一个整数 T (1 \le T \le 100) 。
对于每组测试样例：
第一行输入一个整数 n (1 \le n \le 100) ，表示一共有 n 个人。
接下来的 n - 1 行，每行输入两个整数 u,v (1 \le u,v \le n) ，表示 u 是 v 的父亲，每个人都只能有一个父亲。
下一行两个整数 x,y ，代表询问的两个人。
保证询问一定有答案。

输出格式

输出 T 行，每行包含一个整数，表示询问的两个人的辈分差。

输入样例

2
5
2 1
3 4
3 5
2 3
2 4
6
3 2
3 5
2 1
6 3
6 4
6 1

输出样例

2
3

题意

思路

代码

void solve(){
    int n;
    cin >> n;
    vector<int> fa (n + 1,-1); // fa[x] = y // y是x的父亲
    for(int i = 1;i < n;i++){
        int u,v;
        cin >> u >> v;
        fa[v] = u;
    }
    int x,y;
    cin >> x >> y;
    int now1 = x;
    int cnt1 = 0;
    while(now1 != -1){
        if(now1 == y){
            cout << cnt1 << "\n";
            return;
        }
        cnt1++;
        now1 = fa[now1];
    }
    int cnt2 = 0;
    int now2 = y;
    while(now2 != -1){
        if(now2 == x){
            cout << cnt2 << "\n";
            return;
        }
        cnt2++;
        now2 = fa[now2];
    }
}