这题是经典的DFS题

参考代码

#include<bits/stdc++.h>

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

const int N = 100010, M = N * 2;

int n, m;
int h[N];   // h[i] 表示表头i的第一个结点的下标
int e[M];   // e[i] 表示下标为i的节点的值，即结点e[i]
int ne[M], idx;  // ne[i] 表示下标为i结点的下一个结点的下标
bool st[N];
int limit_w[N];     // 限制功率

ll dqs[N], idxd = 1;    // 用电器的功率和
int stc[N];     // 标记是否是叶子结点

void add(int a, int b)  // 点a指向点b的一条有向边
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

ll dfs(int u)
{
    st[u] = true;   // 标记已经被读过

    ll sum = 0;

    if (stc[u] == 0) sum += limit_w[u];   // 是叶子节点，加上叶子节点的功率
    //bool isLeaf = true;  // 假设当前节点是叶子节点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {   // 如果存在一个未访问的子节点
            //isLeaf = false; // 当前节点不是叶子节点
            sum += dfs(j);  // 统计每个结点作为子树的总功率
        }
    }
    //if (isLeaf) sum += limit_w[u];   // 是叶子节点，加上叶子节点的功率

    dqs[idxd++] = sum;  // 子树的总功率存入数组

    return sum;
}

void solve()
{
    memset(h, -1, sizeof h);    // 初始化

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, c;
        cin >> a >> c;
        add(a, i);  // 建树 从 a --> i
        limit_w[i] = c;   // 限制功率
        stc[a]++;   // 标记非用电器（插排），不是叶子节点
    }

    // 单个电器功率大于2200w，直接"NO"
    for (int i = 1; i <= n; i++) {
        if (stc[i] == 0 and limit_w[i] > 2200) {
            cout << "NO" << endl;
            return;
        }
    }

    ll chazuo = dfs(0);     // 如果所有用电器（叶子节点）的功率之和大于2200W，输出"NO"
    if (chazuo > 2200) {
        cout << "NO" << endl;
        return;
    }

    // 多个用电器功率之和大于2200w，直接"NO"
    for (int i = 1; i <= n; i++) {
        if (dqs[i] > 2200) {
            cout << "NO" << endl;
            return;
        }
    }

    // 排序
    limit_w[++n] = 2200;    // 将总插座的功率加入
    sort(limit_w + 1, limit_w + n + 1);
    sort(dqs + 1, dqs + idxd);


    // 限制功率和用电器需要的功率需对应并且满足
    for (int i = 1; i < idxd; i++) {
        if (limit_w[i] < dqs[i]) {
            cout << "NO" << endl;
            return;
        }
    }

    // 如果满足，输出"YES"
    cout << "YES" << endl;
}

int main()
{
    int t = 1;
    //cin >> t;
    while (t--)
        solve();

    return 0;
}

易错测试用例

5 
0 500
1 700
1 400
2 100
2 300

5
0 100000
1 100000
1 2000
2 100
2 200

4
0 1000
0 1
0 1000
0 800

5
0 1000
0 10000
1 1000
2 1000
2 200

5
0 1000
0 10000
1 1000
2 1000
2 300