分布式系统任务调度

题意

给一棵二叉树（以层序遍历数组表示，-1 代表空节点），每个节点有唯一整数 ID。给定两个节点 ID 和 ，找到它们的最近公共祖先（LCA），然后输出该 LCA 管辖的节点总数（不包含 LCA 自身）。

题目说"层级越低优先级越高"，所以"最低共同主控节点"就是 LCA。如果 是 的祖先，那 LCA 就是 。

思路

层序遍历数组天然支持用下标关系表示父子：对于下标 的节点，左孩子是 ，右孩子是 ，父亲是 。

这题节点数只有 32，所以不需要什么花里胡哨的算法，直接暴力就行。分两步走：

第一步：找 LCA

怎么在数组表示的二叉树里找 LCA？

最简单的方式：先找到 和 在数组中的下标 和 。从 出发，一路往上走到根，把路径上所有下标存到一个集合里。然后从 出发往上走，第一个出现在集合里的下标就是 LCA。

往上走的操作就是 cur = (cur - 1) / 2，直到 cur == 0（根节点）。

第二步：数子树大小

找到 LCA 的下标后，从它出发做一次 BFS/DFS，统计子树中所有非空节点的个数（不算自身）。

复杂度

  • 找节点下标：
  • 找 LCA：（树高）
  • 数子树：
  • 总体

代码

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

int main(){
    int n;
    scanf("%d", &n);
    vector<long long> arr(n);
    for(int i = 0; i < n; i++) scanf("%lld", &arr[i]);
    long long a, b;
    scanf("%lld %lld", &a, &b);

    int idxA = -1, idxB = -1;
    for(int i = 0; i < n; i++){
        if(arr[i] == a) idxA = i;
        if(arr[i] == b) idxB = i;
    }

    // 收集 A 到根的路径
    set<int> ancestorsA;
    int cur = idxA;
    while(cur >= 0){
        ancestorsA.insert(cur);
        if(cur == 0) break;
        cur = (cur - 1) / 2;
    }

    // B 往上走，找到第一个在 A 祖先集合里的
    cur = idxB;
    while(ancestorsA.find(cur) == ancestorsA.end()){
        cur = (cur - 1) / 2;
    }
    int lcaIdx = cur;

    // BFS 数子树节点（不含 LCA 自身）
    int count = 0;
    queue<int> q;
    q.push(lcaIdx);
    while(!q.empty()){
        int idx = q.front(); q.pop();
        if(idx != lcaIdx) count++;
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        if(left < n && arr[left] != -1) q.push(left);
        if(right < n && arr[right] != -1) q.push(right);
    }

    printf("%d\n", count);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextLong();
        long a = sc.nextLong(), b = sc.nextLong();

        int idxA = -1, idxB = -1;
        for (int i = 0; i < n; i++) {
            if (arr[i] == a) idxA = i;
            if (arr[i] == b) idxB = i;
        }

        Set<Integer> ancestorsA = new HashSet<>();
        int cur = idxA;
        while (cur >= 0) {
            ancestorsA.add(cur);
            if (cur == 0) break;
            cur = (cur - 1) / 2;
        }

        cur = idxB;
        while (!ancestorsA.contains(cur)) {
            cur = (cur - 1) / 2;
        }
        int lcaIdx = cur;

        int count = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(lcaIdx);
        while (!q.isEmpty()) {
            int idx = q.poll();
            if (idx != lcaIdx) count++;
            int left = 2 * idx + 1;
            int right = 2 * idx + 2;
            if (left < n && arr[left] != -1) q.add(left);
            if (right < n && arr[right] != -1) q.add(right);
        }

        System.out.println(count);
    }
}

import sys
from collections import deque

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    arr = [int(input_data[idx + i]) for i in range(n)]; idx += n
    a = int(input_data[idx]); idx += 1
    b = int(input_data[idx]); idx += 1

    idxA = idxB = -1
    for i in range(n):
        if arr[i] == a: idxA = i
        if arr[i] == b: idxB = i

    ancestorsA = set()
    cur = idxA
    while cur >= 0:
        ancestorsA.add(cur)
        if cur == 0:
            break
        cur = (cur - 1) // 2

    cur = idxB
    while cur not in ancestorsA:
        cur = (cur - 1) // 2
    lcaIdx = cur

    count = 0
    q = deque([lcaIdx])
    while q:
        idx = q.popleft()
        if idx != lcaIdx:
            count += 1
        left = 2 * idx + 1
        right = 2 * idx + 2
        if left < n and arr[left] != -1:
            q.append(left)
        if right < n and arr[right] != -1:
            q.append(right)

    print(count)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const arr = lines[1].split(/\s+/).map(Number);
    const [a, b] = lines[2].split(/\s+/).map(Number);

    let idxA = -1, idxB = -1;
    for (let i = 0; i < n; i++) {
        if (arr[i] === a) idxA = i;
        if (arr[i] === b) idxB = i;
    }

    const ancestorsA = new Set();
    let cur = idxA;
    while (cur >= 0) {
        ancestorsA.add(cur);
        if (cur === 0) break;
        cur = Math.floor((cur - 1) / 2);
    }

    cur = idxB;
    while (!ancestorsA.has(cur)) {
        cur = Math.floor((cur - 1) / 2);
    }
    const lcaIdx = cur;

    let count = 0;
    const q = [lcaIdx];
    let head = 0;
    while (head < q.length) {
        const idx = q[head++];
        if (idx !== lcaIdx) count++;
        const left = 2 * idx + 1;
        const right = 2 * idx + 2;
        if (left < n && arr[left] !== -1) q.push(left);
        if (right < n && arr[right] !== -1) q.push(right);
    }

    console.log(count);
});