题目描述

难度分:$2100$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(0 \leq a[i] \leq n-1)$。

判断能否构造一棵有$n$个节点的带权满二叉树（每个节点都有$0$或$2$个子节点），满足如下性质：

1. 对于每个非叶节点$x$，$x$到其左右儿子的边权，其中一个是$0$，另一个是$1$。
2. 按照先序遍历访问叶子，根到第$i$个叶子的距离恰好等于$a[i]$。

能否构造？输出YES或NO。

输入样例

2
5
2 1 0 1 1
5
1 0 2 1 3

输出样例

YES
NO

算法

构造+链表模拟

这种题感觉就是神仙题，没灵感直接就牢底坐穿。由于是完全二叉树，因此存在两个叶子节点属于同一个父节点的情况，并且它们到根节点的距离之差为$1$（因为它们到根节点的距离仅仅在父节点往下时发生改变，一条边的权为$0$一条边的权为$1$，更上面的路径是一样的）。因此，可以每次删除两个叶子节点，让它们的父节点继承小的那个权重，此时它们的父节点又变成了新的叶子节点，继续进行后续的删除。

我们可以先把$1$到$n$连接成双端链表，每次删除满足$a[u]$比左邻居或右邻居大$1$的节点$u$，删$n-1$次直到剩最后一个节点，只要最后剩下一个$root$满足$a[root]=0$，就可以构造出符合条件的完全二叉树。每次贪心地选出最大的那个$a[i]$，我们可以先将满足条件的节点加入到一个大根堆中（大根堆按照$a[i]$排序，存入二元组$(a[i],i)$），这样每一轮删除操作选出堆顶删就可以了。删除节点$u$之后，它的左右邻居会连接起来，这样有可能会产生新的待删节点，记得将其加入到大根堆中。

为了避免二元组的大根堆中重复加入相同的$pair$，在实现时用一个有序集合来代替优先队列，不影响时间复杂度。

复杂度分析

时间复杂度

插入到堆中的元素数量在$O(n)$级别，因此初始化的时间复杂度为$O(nlog_2n)$。之后需要删除$n-1$个点，每次删除会有往堆中插入元素的操作，因此时间复杂度还是$O(nlog_2n)$。

空间复杂度

堆中会存$O(n)$级别的待删元素，链表的空间也是$O(n)$，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

const int N = 200010;
int T, n, a[N], L[N], R[N];

void solve() {
    scanf("%d", &n);
    R[0] = 1, L[n + 1] = n;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        L[i] = i - 1, R[i] = i + 1;
    }
    set<PII> st;
    for(int i = 1; i <= n; i++) {
        if(i > 1 && a[i - 1] == a[i] - 1) st.insert({a[i], i});
        if(i < n && a[i + 1] == a[i] - 1) st.insert({a[i], i});
    }
    bool ok = true;
    for(int i = 1; i < n; i++) {
        if(st.empty()) {
            ok = false;
            break;
        }
        int u = st.rbegin()->second;
        int l = L[u], r = R[u];
        if((l > 0 && a[l] == a[u] - 1) || (r <= n && a[r] == a[u] - 1)) {
            st.erase({a[u], u});
            R[l] = r, L[r] = l;
            if(l > 0 && r <= n) {
                if(a[l] == a[r] - 1) st.insert({a[r], r});
                if(a[r] == a[l] - 1) st.insert({a[l], l});
            }
        }else {
            ok = false;
            break;
        }
    }
    if(a[R[0]] != 0) ok = false;
    puts(ok? "YES": "NO");
}

int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}