专栏文章

题解：P3884 [JLOI2009] 二叉树问题

DDoraeman
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio58g63
此快照首次捕获于
2025/12/02 13:34
3 个月前
此快照最后确认于
2025/12/02 13:34
3 个月前
查看原文
这道题涉及二叉树基础知识，接下来分为 33 部分讲解。

二叉树

树基础（OI Wiki）；二叉树（百度百科）。
总之，树就是一种数据结构，形似生活中倒挂的树而得名。
二叉树是一种特殊的数，树上每个节点最多只有 22 个子节点。

各节点深度 &\& 求第 11 个答案

在这道题中，33 个答案全部都依赖于各节点深度。
那么我们该如何求各节点深度呢？
写 dfs 深度优先搜索，遍历整棵二叉树。
遍历过程：
  1. 得到当前树的根节点，并记录这个根节点的深度。
    注：整棵树的根节点的深度为 11。
  2. 以根的左节点为一棵新树的根，遍历左子树。
    其深度为当前根的深度 +1+1。
  3. 以根的右节点为另一棵新树的根，遍历右子树。
    其深度也为当前根的深度 +1+1。
  4. 当遇到叶子结点（没有子节点），当前遍历结束，返回上一层完成接下来的遍历。
按照以上遍历过程，就可以求出所有节点的深度。

求各节点深度代码

CPP
void get_depth(int x, int d){
    depth[x] = d;
    if(Ls[x]) get_depth(Ls[x], d+1);
    if(Rs[x]) get_depth(Rs[x], d+1);
}
求出所有节点的深度之后，就可以求各节点深度的最大值。得到的值就是题目要求的第 11 个答案。

二叉树的宽度

看这道题中“树的宽度”的定义：同一层最多的结点个数。
其中“同一层”的意思也就是深度相同。
因此，直接把所有深度相同的节点放在一起计算个数，最后求哪个深度的节点数量最多（最大值），就得到了第 22 个答案。

求二叉树宽度的代码

CPP
int ans2 = 0;
for(int i=1; i<=n; i++)
    width[depth[i]]++,
    ans2 = max(width[depth[i]], ans2);
cout << ans2 << '\n';

节点距离

看“距离”的定义：从起始节点到结束节点的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。

思路

可以先求出两个节点 x,yx,y 的最深公共祖先 ff（也就是 x,yx,y 的若干个公共祖先中辈分最小的）。
然后计算 x,fx,f 的深度落差，也就是起始节点向根节点的边数。这部分要 ×2\times2。
再计算 y,fy,f 的深度落差，也就是向叶节点方向（结束节点）的边数。
最后求和，得到答案。

最深公共祖先

把两个节点分别向根节点遍历，遍历途中一直都只有一条向上找父节点的路。
一直走这条路并把沿途经过的各个“父亲”都记录为祖先之一。
最后比较 x,yx,y 的祖先当中最靠前（最先记录）的公共祖先。

求最深公共祖先的代码

CPP
void dfsx(int x){
    fx.push_back(x);
    if(x == 1) return;
    dfsx(f[x]);
}
void dfsy(int y){
    fy.push_back(y);
    if(y == 1) return;
    dfsy(f[y]);
}
int main(){
    dfsx(x); dfsy(y);
    int comf = 0;
    for(int i=0; !comf&&i<fx.size(); i++)
        for(int j=0; !comf&&j<fy.size(); j++)
            if(fx[i] == fy[j]) comf = fx[i];
}
我们就成功将最深公共祖先记录在了 comfcomf 里。
注意：以上代码虽然没有写 break，但是循环条件内加入了 !comf。所以当 comf 变量有值时，循环就会结束而不会去寻找“辈分更大”的公共祖先。

根据公共祖先求距离

最后，我们只要按照思路中提到的：求节点与公共祖先的深度差，就可以得到第 33 个答案。

根据公共祖先求距离的代码

CPP
int go(int x, int y){
    return abs(depth[x] - depth[y]);
}
int main(){
    int ans3 = go(x, comf)*2 + go(comf, y);
    cout << ans3 << '\n';
}

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 105;

int n, f[N], Ls[N], Rs[N], depth[N], width[N];
vector <int> fx, fy;

// 求各根节点深度 
void get_depth(int x, int d){
    depth[x] = d;
    if(Ls[x]) get_depth(Ls[x], d+1);
    if(Rs[x]) get_depth(Rs[x], d+1);
}

// 求祖先 
void dfsx(int x){
    fx.push_back(x);
    if(x == 1) return;
    dfsx(f[x]);
}
void dfsy(int y){
    fy.push_back(y);
    if(y == 1) return;
    dfsy(f[y]);
}

// 求深度差 
int go(int x, int y){
    return abs(depth[x] - depth[y]);
}

int main(){
    cin >> n;
    for(int i=1; i<n; i++){
        int u, v; cin >> u >> v;
        f[v] = u;
        if(!Ls[u]) Ls[u] = v;
        else Rs[u] = v;
    }
    
    get_depth(1, 1);

    // Ans #1
    int ans1 = 0;
    for(int i=1; i<=n; i++)
        ans1 = max(depth[i], ans1);
    cout << ans1 << '\n';

    // Ans #2 
    int ans2 = 0;
    for(int i=1; i<=n; i++)
        width[depth[i]]++, ans2 = max(width[depth[i]], ans2);
    cout << ans2 << '\n';

    // Ans #3 
    // 求最深公共祖先 
    int x, y; cin >> x >> y;
    dfsx(x); dfsy(y);
    int comf = 0;
    for(int i=0; !comf&&i<fx.size(); i++)
        for(int j=0; !comf&&j<fy.size(); j++)
            if(fx[i] == fy[j])
                comf = fx[i];

    // 求距离 
    int ans3 = go(x, comf)*2 + go(comf, y);
    cout << ans3 << '\n';
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...