2020-07-15 [JLOI2009]二叉树问题

题目：https://www.luogu.com.cn/problem/P3884

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x*10+c-'0';
        c = getchar();
    }
    return x*f;
}

struct node{
    int l,r,d,w,val;
}a[101];//记录每个节点的左右节点

int n,u,v;

int depth , length, disu = 0 , disv=0;

void dfs(int root,int step){
    if( u==v ){
        cout<<disu*2+disv<<"\n";//注意审题
             //cout<<"QAQ";
        exit(0);//直接退出
    }
    if(a[u].d==a[v].d){
        v= a[v].val;
        u= a[u].val;
        disu++;
        disv++;
    }else if(a[u].d<a[v].d){
        v=a[v].val;
        disv++;
    }else{
        u=a[u].val;
        disu++;
    }
    dfs(u,v);
}

int main(){
    n = read();//输入n
    a[1].d = 1;
    for(int i=1;i<=n-1;i++){
        u = read();
        v = read();
        a[v].val = u;
        a[v].d = a[u].d + 1;
        depth = max(depth,a[v].d);
        a[ a[v].d ].l ++;
        length = max(length,a[ a[v].d ].l);
    }
    cout<<depth<<endl<<length<<endl;
    u = read();
    v = read();
    dfs(u,v);//从1号节点，深度为1开始搜索
    return 0;
}
/*
10
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6
*/