只有第一个点没过... 我的思路和其他人的不大一样,我是建立一颗动态的二叉树,在插入节点时先找到父节点然后动态分配空间.在寻找父节点时把路径记录下来,这样时间复杂度大大降低(但不知道哪里有问题) 代码:

#include <unordered_map>
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

// #define NULL nullptr
struct node
{
    int val;
    node *l;
    node *r;
    node(int x = 1, node *l = NULL, node *r = NULL) : val(x), l(NULL), r(NULL) {}
} *root;
int n, depth, width, t1, t2;
unordered_map<int, string> htable; // hash表,记录每个节点的位置

void Value(node *&n, int num, const char *end)
{
    if (n->val == t1)
    {
        if (n->l == NULL)
        {
            n->l = new node(t2);
            htable[t2] = htable[t1] + "0";
        }
        else
        {
            n->r = new node(t2);
            htable[t2] = htable[t1] + "1";
        }
        return;
    }
    if (end[num] == '0')
        Value(n->l, num + 1, end);
    else
        Value(n->r, num + 1, end);
}

void Insert() // bfs
{
    if (htable[t1] != "" && t1) // 如果已经知道其位置,直接赋值
    {
        Value(root, 0, htable[t1].c_str());
        return;
    }
    queue<node *> q;
    q.push(root);
    node *n;
    int size;
    while (!q.empty())
    {
        /*
        queue<node *> qt = q;
        for (int i = 0; i < q.size(); i++)
        {
            cout << qt.front()->val << " ";
            cout << htable[qt.front()->val] << "\t";
            qt.pop();
        }
        cout << endl;
        */
        size = q.size();
        if (!t1) {
            width = max(size, width); // 记录最大宽度
            depth++; // 记录深度
        }
        for (int i = 0; i < size; i++) // 二叉树bfs:每次处理一层
        {
            n = q.front();
            q.pop();
            if (n->val == t1 && t1)
            {
                Value(root, 0, htable[n->val].c_str());
                return;
            }
            if (n->l != NULL)
            {
                htable[n->l->val] = htable[n->val] + "0";
                q.push(n->l);
            }
            if (n->r != NULL)
            {
                htable[n->r->val] = htable[n->val] + "1";
                q.push(n->r);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    root = new node();
    /*
    freopen("p3884.in", "r", stdin);
    freopen("p3884.out", "w", stdout);
    */
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        cin >> t1 >> t2;
        Insert();
        /*
        for (auto it = htable.begin(); it != htable.end(); it++)
            cout << it->first << ":" << it->second << ' ';
        cout << endl;
        */
    }
    t1 = 0;
    Insert();
    cout << depth << endl
         << width << endl;

    int n;
    int tt1, tt2;
    cin >> tt1 >> tt2;
    int m1 = strlen(htable[tt1].c_str()), m2 = strlen(htable[tt2].c_str());
    for (n = 0; n < min(m1, m2); n++)
    {
        if (htable[tt1][n] != htable[tt2][n])
            break;
    }
    cout << m1 * 2 + m2 - 3 * n;
    return 0;
}