解题思路

• 公司组织被简化为一棵二叉树，结点表示员工，父结点是上级，父结点“管理”其整棵子树的所有员工。
• 输入给出按层序（完全二叉树下标方式）展开的数组，-1 表示该位置没有员工；再给出两名员工工号 u、v。
• 要求：找到两人级别最低的共同主管，并返回该主管子树中的员工总数（不含主管本人）。

核心做法：

1. 数组建树 + 反向索引 用数组存树，建立“工号 → 数组下标”的映射。下标 i 的父结点是 (i-1)//2，左右子为 2*i+1, 2*i+2（越界或值为 -1 视为不存在）。

2. LCA（最低公共祖先）

   • 只在“下标树”上移动即可，无需真正建链表结构。
   • 先把较深的下标逐级提升到同一深度，再同时向上移动直到相遇，得到 LCA 下标。

3. 子树规模统计 从 LCA 下标出发做 DFS/栈遍历，统计其子树中非 -1 结点数 sz；答案为 sz - 1（不计主管本人）。

为什么可行：数组层序就是完全二叉树的下标体系，父子关系由下标公式唯一确定；LCA 的“抬高再同步上跳”对任意树都成立；子树统计只需跳过越界和 -1。

复杂度分析

• 设数组长度为 n。
• 建立映射：O(n)；
• LCA：每次上跳一步，最坏 O(h)，h ≤ ⌊log2(n)⌋ + 1；
• 子树统计：访问每个存在的结点一次，O(n)（但仅遍历 LCA 子树，实际更小）。
• 时间复杂度：O(n)；空间复杂度：O(n)（映射与递归/栈深度）。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意：数组表示的二叉树中，求两员工的最低共同主管，并返回其子树人数（不含主管）
import sys

def depth_idx(i: int) -> int:
    """计算数组下标 i 的深度（根为 0 层）"""
    d = 0
    while i > 0:
        i = (i - 1) // 2
        d += 1
    return d

def lca_index(i: int, j: int) -> int:
    """在数组树中求下标 i 和 j 的 LCA 下标"""
    di, dj = depth_idx(i), depth_idx(j)
    # 先把较深者抬到同一深度
    while di > dj:
        i = (i - 1) // 2
        di -= 1
    while dj > di:
        j = (j - 1) // 2
        dj -= 1
    # 同步向上直到相遇
    while i != j:
        i = (i - 1) // 2
        j = (j - 1) // 2
    return i

def subtree_size(arr, n, root_idx: int) -> int:
    """统计以 root_idx 为根的子树结点数（包含根，跳过 -1 和越界）"""
    # 用显式栈避免递归深度问题
    if root_idx >= n or arr[root_idx] == -1:
        return 0
    stack = [root_idx]
    cnt = 0
    while stack:
        u = stack.pop()
        if u >= n or arr[u] == -1:
            continue
        cnt += 1
        l = 2 * u + 1
        r = 2 * u + 2
        if l < n:
            stack.append(l)
        if r < n:
            stack.append(r)
    return cnt

def solve():
    data = sys.stdin.read().strip().split()
    # 输入：n，接着 n 个整数的层序数组，最后两个工号
    n = int(data[0])
    arr = list(map(int, data[1:1 + n]))
    u, v = map(int, data[1 + n:1 + n + 2])

    # 建立工号到下标的映射
    pos = {}
    for i, x in enumerate(arr):
        if x != -1:
            pos[x] = i

    iu = pos[u]
    iv = pos[v]

    # 求 LCA 下标
    p = lca_index(iu, iv)

    # 统计子树规模，答案不含主管本人
    ans = subtree_size(arr, n, p) - 1
    print(ans)

if __name__ == "__main__":
    solve()

Java

// 请使用 Java 17+ 编译运行
// 功能：数组形式的二叉树中，求两员工的最低共同主管并统计其子树人数（不含主管）
import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static long[] a;          // 用 long 存工号，-1 表示不存在
    static HashMap<Long, Integer> pos = new HashMap<>();

    // 计算下标深度（根深度为 0）
    static int depth(int i) {
        int d = 0;
        while (i > 0) {
            i = (i - 1) / 2;
            d++;
        }
        return d;
    }

    // 下标 LCA
    static int lcaIndex(int i, int j) {
        int di = depth(i), dj = depth(j);
        while (di > dj) { i = (i - 1) / 2; di--; }
        while (dj > di) { j = (j - 1) / 2; dj--; }
        while (i != j) {
            i = (i - 1) / 2;
            j = (j - 1) / 2;
        }
        return i;
    }

    // 统计以 rootIdx 为根的子树大小（包含根；跳过 -1 和越界）
    static int subtreeSize(int rootIdx) {
        if (rootIdx >= n || a[rootIdx] == -1) return 0;
        Deque<Integer> st = new ArrayDeque<>();
        st.push(rootIdx);
        int cnt = 0;
        while (!st.isEmpty()) {
            int u = st.pop();
            if (u >= n || a[u] == -1) continue;
            cnt++;
            int l = 2 * u + 1, r = 2 * u + 2;
            if (l < n) st.push(l);
            if (r < n) st.push(r);
        }
        return cnt;
    }

    public static void main(String[] args) throws Exception {
        // 读入：n，接着 n 个整数（层序数组），接着两个工号
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        n = Integer.parseInt(s1.trim());
        String s2 = br.readLine();
        StringTokenizer st = new StringTokenizer(s2);
        a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }
        String s3 = br.readLine();
        StringTokenizer st3 = new StringTokenizer(s3);
        long u = Long.parseLong(st3.nextToken());
        long v = Long.parseLong(st3.nextToken());

        // 建立工号到下标的映射
        for (int i = 0; i < n; i++) {
            if (a[i] != -1) pos.put(a[i], i);
        }

        int iu = pos.get(u);
        int iv = pos.get(v);
        int p = lcaIndex(iu, iv);
        int ans = subtreeSize(p) - 1; // 不含主管自身
        System.out.println(ans);
    }
}

C++

// 功能：数组表示的二叉树中，求两员工的最低共同主管，并输出其子树人数（不含主管）
#include <bits/stdc++.h>
using namespace std;

int depthIdx(int i) {
    int d = 0;
    while (i > 0) { i = (i - 1) / 2; ++d; }
    return d;
}

int lcaIndex(int i, int j) {
    int di = depthIdx(i), dj = depthIdx(j);
    while (di > dj) { i = (i - 1) / 2; --di; }
    while (dj > di) { j = (j - 1) / 2; --dj; }
    while (i != j) { i = (i - 1) / 2; j = (j - 1) / 2; }
    return i;
}

int subtreeSize(const vector<long long>& a, int n, int rootIdx) {
    if (rootIdx >= n || a[rootIdx] == -1) return 0;
    int cnt = 0;
    vector<int> st; st.push_back(rootIdx);
    while (!st.empty()) {
        int u = st.back(); st.pop_back();
        if (u >= n || a[u] == -1) continue;
        ++cnt;
        int l = 2 * u + 1, r = 2 * u + 2;
        if (l < n) st.push_back(l);
        if (r < n) st.push_back(r);
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    long long u, v; cin >> u >> v;

    // 建立工号到下标的映射
    unordered_map<long long, int> pos;
    pos.reserve(n * 2);
    for (int i = 0; i < n; ++i) if (a[i] != -1) pos[a[i]] = i;

    int iu = pos[u], iv = pos[v];
    int p = lcaIndex(iu, iv);
    int ans = subtreeSize(a, n, p) - 1; // 不含主管本人
    cout << ans << "\n";
    return 0;
}

题目内容

你正在开发一个企业的组织架构管理系统，公司的组织架构被 简化表示为一棵二叉树。树的每个节点代表一个员工，树的层级越低则级别越高，高级别作为主管，管辖其子树涉及的所有员工。

每个人有一个唯一的工号，工号以整数值表示，范围是 $[0,10^9]$ 。

此管理系统需要提供一个统计能力，对任意两名员工，找到他们级别最低的共同主管，返回当前主管管辖的人员个数。

注意：

• 如果两名员工本身存在上下级关系，共同主管为级别较高的员工。

• 员工总数 $<= 10^5$。

• 待检索员工的工号一定在给定的二叉树中，且两位员工工号不同。

输入描述

• 第一行为一个整数，表示输入的节点个数。

• 第二行为一行数字，由空格分割，每个数字表示一颗满一叉树各层从左到右的节点。值为员工工号，$-1$ 代表该节点不存在。

例 $1$ $2$ $3$ $4$ $-1$ $5$ $-1$ $-1$ $6$ 可转化为下图的一又树，

• 第三行为两个数字，用空格分割，表示待检索的两名员工工号，例如：$5$ $1$ 。

输出描述

输出级别最低的共同主管管辖的人员总个数(不包括自身)。

样例1

输入

12
2 3 5 1 7 6 8 -1 -1 0 4 -1
0 3

输出

4

说明

$0$ 和 $3$ 存在上下级关系，共同主管为 $3$ ，管辖总人数为 $4$ 。

样例2

输入

9
1 2 3 4 -1 5 -1 -1 6
5 4

输出

5

说明

$5$ 和 $4$ 的共同主管为节点 $1$ ，管辖总人数为 $5$ 。