代码抛出std::bad_alloc错误求助：已分配足够内存仍报错

问题现象 #

代码运行时抛出std::bad_alloc错误，错误信息如下：

terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc

尝试按引用传递参数后问题仍未解决，原代码如下：

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

void dfs(ll root , vector<vector<ll>> &graph , vector<ll> &weights , ll max_weight , ll &ans)
{
    for(auto adj : graph[root])
    {
        ans = max(ans , (max_weight - weights[adj]) );
        max_weight = max( max_weight , weight[adj]);
        dfs(adj , graph , weights , max_weight , ans);
    }
}

int main() {
    ll n;
    cin>>n;
    vector<ll>a(n+1 , 0);
    vector<vector<ll>>v(n+1);
    
    for(ll i=0 ;i<n;i++)
        {
            ll wt;cin>>wt;a[i]=wt;
        }
    ll root = -1;
    for(ll i=0 ;i<n;i++)
    {
        ll p;cin>>p;
        if(p == -1)root = i;
        v[p-1].push_back(i);
    }
    
    ll ans = INT_MIN;
    ll wt = a[root];
    dfs(root , v , a , wt , ans);
    cout<<ans<<endl;
    
    return 0;
}

错误原因分析 #

1. 数组越界破坏内存：当父节点p=-1时，执行v[p-1].push_back(i)等价于访问v[-2]，属于严重的越界操作，会直接破坏vector的内部内存结构，进而触发std::bad_alloc错误（内存损坏后，后续内存操作会出现异常）。
2. 变量拼写错误：DFS函数中weight[adj]应为weights[adj]，少了字母s，访问未定义变量会导致未定义行为，可能加剧内存问题。
3. 根节点处理遗漏：当p=-1时（即当前节点是根节点），不应执行添加到父节点邻接表的操作，因为根节点没有父节点。

修正后的代码 #

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

void dfs(ll root, vector<vector<ll>> &graph, vector<ll> &weights, ll max_weight, ll &ans)
{
    for (auto adj : graph[root])
    {
        ans = max(ans, max_weight - weights[adj]);
        // 避免修改当前max_weight影响同层其他节点，为每个子节点单独计算新最大值
        ll new_max = max(max_weight, weights[adj]);
        dfs(adj, graph, weights, new_max, ans);
    }
}

int main()
{
    ll n;
    cin >> n;
    vector<ll> a(n); // 节点索引为0到n-1，无需额外分配n+1空间
    vector<vector<ll>> v(n);

    for (ll i = 0; i < n; i++)
    {
        ll wt;
        cin >> wt;
        a[i] = wt;
    }

    ll root = -1;
    for (ll i = 0; i < n; i++)
    {
        ll p;
        cin >> p;
        if (p == -1)
        {
            root = i;
            continue; // 根节点无父节点，跳过添加操作
        }
        v[p - 1].push_back(i); // 将输入的1-based父节点索引转为0-based
    }

    ll ans = INT_MIN;
    dfs(root, v, a, a[root], ans);
    cout << ans << endl;

    return 0;
}

额外说明 #

修正后的代码还修复了一个逻辑问题：原DFS中直接修改max_weight会导致同层后续节点使用更新后的值，而正确的做法是为每个子节点单独计算新的最大值，不影响同层其他节点的遍历逻辑。

内容的提问来源于stack exchange，提问作者Preethi