[JLOI2009] 二叉树问题

题意

给出根为 1 的树，求最大深度、最大层宽，以及指定 x 到 y 的特殊距离：向根方向每条边代价 2，向叶方向每条边代价 1。

思路

BFS 从根计算每个节点深度；相同深度的节点数用 Counter 统计，最大频率就是宽度。

求距离时，先把 x 到根的全部祖先放入集合，再让 y 沿父指针上升，第一个属于集合的节点就是 LCA。于是：

2(depth_x-depth_{lca})+(depth_y-depth_{lca})

Python 知识

Counter(depth[1:]) 直接统计每层节点数。
祖先集合提供平均 $O(1)$ 成员判断，适合 n<=100 的朴素 LCA。
print(...,sep="\n") 一次输出三个独立答案。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：Counter、集合与 deque。
/home/rainboy/mycode/hugo-blog/content/program_language/python/bfs_shortest.md：层次 BFS。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35from collections import Counter, deque


n = int(input())
children = [[] for _ in range(n + 1)]
parent = [0] * (n + 1)

for _ in range(n - 1):
    father, child = map(int, input().split())
    children[father].append(child)
    parent[child] = father

x, y = map(int, input().split())
depth = [0] * (n + 1)
depth[1] = 1
queue = deque([1])
while queue:
    node = queue.popleft()
    for child in children[node]:
        depth[child] = depth[node] + 1
        queue.append(child)

ancestors = set()
node = x
while node:
    ancestors.add(node)
    node = parent[node]

lca = y
while lca not in ancestors:
    lca = parent[lca]

level_count = Counter(depth[1:])
distance = 2 * (depth[x] - depth[lca]) + depth[y] - depth[lca]
print(max(depth), max(level_count.values()), distance, sep="\n")

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72/**
 * P3884 二叉树问题
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

// 邻接表存无向树
int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], edge_cnt;
int parent[MAXN];   // 父结点
int depth[MAXN];    // 深度（根为 1）
int cnt[MAXN];      // 每一层的结点数
int n;

void add_edge(int u, int v) {
    ++edge_cnt;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// DFS 求深度，记录父结点
void dfs(int u, int dep) {
    depth[u] = dep;
    ++cnt[dep];
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == parent[u]) continue;
        parent[v] = u;
        dfs(v, dep + 1);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    int x, y;
    scanf("%d%d", &x, &y);

    // 根为 1，DFS 求深度、宽度
    dfs(1, 1);
    int max_depth = *max_element(depth + 1, depth + n + 1);
    int max_width = *max_element(cnt + 1, cnt + max_depth + 1);

    // 求 LCA：先将 x 和 y 提到同一深度
    int tx = x, ty = y;
    while (depth[tx] > depth[ty]) tx = parent[tx];
    while (depth[ty] > depth[tx]) ty = parent[ty];
    // 再一起上跳
    while (tx != ty) {
        tx = parent[tx];
        ty = parent[ty];
    }
    int lca = tx;
    // 题目规定：x 到 y 的距离 = 2*(depth[x]-depth[lca]) + depth[y]-depth[lca]
    int dist = 2 * (depth[x] - depth[lca]) + (depth[y] - depth[lca]);

    printf("%d\n%d\n%d\n", max_depth, max_width, dist);
    return 0;
}

复杂度

BFS 与两条祖先链均为 $O(n)$ ，空间复杂度 $O(n)$ 。

总结

树上距离先找 LCA 再拆成“向上段”和“向下段”；本题两种方向权值不同，不能直接用普通边数公式。

[JLOI2009] 二叉树问题

目录

题意

思路

Python 知识

代码

复杂度

总结