树上的操作

/*
题目思路：
1. 使用数组 `locks` 记录每个节点的锁状态，使用 `parent` 数组存储父节点信息。
2. 使用 `children` 数组列表记录子节点。
3. `lock` 方法尝试锁定节点。
4. `unlock` 方法尝试解锁节点。
5. `upgrade` 方法检查条件并执行升级操作。
6. 通过 Java Stream 简化子孙节点的遍历和检查。
*/

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class LockingTree {
    private int[] parent;
    private int[] locks;
    private List<List<Integer>> children;

    public LockingTree(int[] parent) {
        this.parent = parent;
        this.locks = new int[parent.length];
        Arrays.fill(locks, -1);
        this.children = IntStream.range(0, parent.length)
                .mapToObj(i -> new ArrayList<Integer>())
                .collect(Collectors.toList());
        IntStream.range(1, parent.length).forEach(i -> children.get(parent[i]).add(i));
    }

    public boolean lock(int num, int user) {
        if (locks[num] == -1) {
            locks[num] = user;
            return true;
        }
        return false;
    }

    public boolean unlock(int num, int user) {
        if (locks[num] == user) {
            locks[num] = -1;
            return true;
        }
        return false;
    }

    public boolean upgrade(int num, int user) {
        if (locks[num] != -1 || hasLockedAncestor(num) || !hasLockedDescendant(num)) {
            return false;
        }
        unlockAllDescendants(num);
        locks[num] = user;
        return true;
    }

    private boolean hasLockedAncestor(int num) {
        for (int i = parent[num]; i != -1; i = parent[i]) {
            if (locks[i] != -1) return true;
        }
        return false;
    }

    private boolean hasLockedDescendant(int num) {
        return children.get(num).stream().anyMatch(child -> locks[child] != -1 || hasLockedDescendant(child));
    }

    private void unlockAllDescendants(int num) {
        children.get(num).forEach(child -> {
            locks[child] = -1;
            unlockAllDescendants(child);
        });
    }
}