J.虚树

题目描述

小 H 有有根树一棵树，这棵树有一个特殊性质：每个节点的父亲的编号都比这个节点的编号小。 小 H 不告诉小 G 他的树的具体情况，只告诉小 G 每个节点的度数，小 G 想知道是否真的存在这样一棵树。

输入

第一行输入一个整数 T，表示数据组数。 之后对于每组数据，第一行输入一个整数 n，表示树上点的个数。第二行包含 n 个整数，其中第 i 个整数表示第 i 个点的度数。 $T≤10^6, 1≤∑n≤10^6$

输出

对于每组数据，输出 “Yes” 表示存在这样的一棵树，”No” 表示不存在这样的树，每组数据占一行。

示例

5
10
2 1 1 1 1 1 1 1 1 8
6
5 5 4 1 5 3
10
5 1 1 1 1 1 1 1 1 5
9
4 2 2 2 1 1 1 2 1
3
1 3 3

No
No
No
Yes
No

注意

树： n 个节点，n−1 条边的连通图。 节点度数： 每个节点所连接的边的条数

思路

这个题我最开始的思路就是维护一个滑动窗口，但是最简化的思路其实是:

维护还剩多少条连向儿子的边。 每次新增一个节点，会消耗一条连向儿子的边，之后会增加 $d_i​−1$ 条连向儿子的边。 时刻维护还剩下多少条连向儿子的边即可，需要保证每个节点都有父亲，以及整个过程结束后没有连向儿子的边。

核心代码

So, code will be like…

    int n; cin >> n;
    int s; cin >> s;
    int flag = 1;
    if (s >= n) flag = 0;
    for (int i = 1; i < n; i++)
    {
        if (s == 0) flag = 0;
        s--;
        int x; cin >> x;
        if (x > n - i) flag = 0;
        s += x - 1;
    }
    if (flag && s == 0) cout << "Yes" << endl;
    else cout << "No" << endl;

Very ez!