P7925 童年题解

bluewindde · 2023-08-01 14:47:38 · 题解

upd 2023.8.1：修改了题解的表述错误。

解法

首先，用一个正常人的思维，我们只应该在能赚的前提下进入一颗子树，所以需要先预处理出进入以节点 i 为根节点的子树的进入的需求 need_i。然后再用 bfs 统计答案。

预处理

那么应该怎么处理子树的进入需求呢？

我们可以使用 dfs，在回溯时处理需求。这里有两种情况：

节点 u 不是鸟巢，即 a_u\ge0，此时不需要进入需求，need_u=0。
节点 u 是鸟巢，即 a_u<0。
此时把节点 u 的子节点加入优先队列，记录当前总的收入 tot。
每次循环取出优先队列中 need_v 最小的节点 v。
若 tot-need_u\ge0，意味着搜索到可以赚的点，此时退出循环；
若 tot<need_v，意味着当前的收入不足以进入节点 v，则使 tot\gets need_v。
在循环结束时，将 tot 加上节点 v 的权值 a_v，并把节点 v 的所有子节点加入优先队列。
退出循环后，一定要再判断一次是否满足 tot-need_u\ge0。如果没有搜索到可以赚的点，意味着无论如何都会亏，所以不走这棵子树，将 need_u\gets\inf。

统计答案

用 bfs 统计，先向优先队列内推入根节点，令 ans\gets s，每次取出优先队列中 need_v 最小的节点 v。若 ans<need_v，则退出循环。否则将 ans 加上 a_v，并把 v 的子节点推入优先队列。

更多的内容可以看代码注释。

AC 代码

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

struct node {
    int need,index;
    inline node(int n,int i):need(n),index(i) {}
    inline bool operator<(const node &b) const { // 重载比较函数 记得加 const
        return need>b.need;
    }
};
priority_queue<node> to_vis;

int n,s;
int fa[6005],a[6005],need[6005];
vector<int> child[6005];

inline void clear() {
    while(!to_vis.empty()) {
        to_vis.pop();
    }
}

inline void dfs(int u) {
    clear();
    for(auto i:child[u]) { // 优先处理子节点
        dfs(i);
    }
    if(a[u]>=0) { // 没有鸟巢，所以进入条件为0
        need[u]=0;
        return ;
    }
    clear();
    for(auto i:child[u]) {
        to_vis.push(node(need[i],i));
    }
    need[u]-=a[u]; // 要给这个节点上的鸟的苹果的数量
    bool flag=false;
    int tot=0;
    while(!to_vis.empty()) {
        if(tot-need[u]>=0) { // 搜索到可以赚的点，退出
            flag=true;
            break;
        }
        node x=to_vis.top();
        to_vis.pop();
        if(tot<need[x.index]) {
            need[u]+=need[x.index]-tot; // 排除这个点，继续尝试
            tot=need[x.index];
        }
        tot+=a[x.index]; // 向子树加入新的点
        for(auto i:child[x.index]) { // 并且把这个点的子节点加进队列
            to_vis.push(node(need[i],i));
        }
    }
    if(tot-need[u]>=0) { // 搜索到可以赚的点，退出
        flag=true;
    }
    if(!flag) {
        need[u]=1e18; // 无论如何都会亏，所以不走这棵子树
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>s;
    for(int i=2;i<=n;++i) {
        cin>>fa[i];
        child[fa[i]].push_back(i);
    }
    for(int i=1;i<=n;++i) {
        cin>>a[i];
    }
    dfs(1);
    clear();
    to_vis.push(node(need[1],1));
    int ans=s;
    while(!to_vis.empty()) {
        node x=to_vis.top();
        to_vis.pop();
        if(ans<need[x.index]) { // 没有达到任何一棵子树可以进入的要求，退出
            break;
        }
        ans+=a[x.index];
        for(auto v:child[x.index]) {
            to_vis.push(node(need[v],v));
        }
    }
    cout<<ans;
    return 0;
}

注意事项

如果用 auto 关键字遍历列表，一定要记得选 -std=c++14 或者更高。

优先队列不能用 clear 方法清空，需要手写循环来清空。

开 long long！！！

P7925 童年 题解

解法

预处理

统计答案

AC 代码

注意事项

P7925 童年题解