M-Monster Hunter

题意

给定一个以1为根的树，树上每个结点都有一个怪物，如果一个结点的父亲上的怪物没有被打败，则不能攻击这个结点的怪物，打败一个结点上怪物需要花费这个只怪物和这个结点子结点上任然存活的怪物的hp之和的代价。

主人公有一个技能，可以花费0的代价，不受任何限制地任意消灭一只怪物

求，发动0，1，2，，，n次技能时，分别的最小代价

题姐

感觉上是dp，仔细思考一下，确实是dp

大家可以去练练树上背包问题

我们定义，表示为在以i为根的子树上，表示我们使用了多少次技能，表示假设当前根的父结点被用技能消灭或没有用技能消灭.

用树上背包的做法去求即可, 时间复杂度为，可以看作树上每个点对都遍历了一次

代码

#include <bits/stdc++.h>

const int N = 2e3+10;

typedef long long ll;

std::vector<int> h[N];
ll p[N], hp[N];
int n;

std::vector<std::array<ll,2>> dfs(int u) {
    if(!h[u].size()) {
        std::vector<std::array<ll,2>> res;
        res.push_back({hp[u],hp[u]*2});
        res.push_back({0,0});
        return res;
    }
    
    std::vector<std::array<ll,2>> now(1,{0ll,0ll});
    for(auto v:h[u]) {
        auto res = dfs(v);
        std::vector<std::array<ll,2>> t(now.size()+res.size()-1,{(ll)2e14,(ll)2e14});
        for(int i=0;i<now.size();i++) 
            for(int j=0;j<res.size();j++) {
                t[i+j][0] = std::min(t[i+j][0],now[i][0]+res[j][0]);
                t[i+j][1] = std::min(t[i+j][1],now[i][1]+res[j][1]);
            }
        now.swap(t);
    }
    
    std::vector<std::array<ll,2>> res(now.size()+1, {(ll)2e14,(ll)2e14});
    for(int i=0;i<res.size();i++) {
        res[i][0] = now[i][1]+hp[u];
        res[i][1] = now[i][1]+hp[u]*2;
        if(i) res[i][0] = std::min(now[i-1][0],res[i][0]);
        if(i) res[i][1] = std::min(now[i-1][0],res[i][1]);
    }
    return res;
}

void solve()
{
    std::cin >> n;
    for(int i=2;i<=n;i++) {
        std::cin >> p[i];
        h[p[i]].push_back(i);
    }
    for(int i=1;i<=n;i++) std::cin >> hp[i];
    
    auto res = dfs(1);
    
    for(auto [u,v]:res) std::cout << u << " ";
    std::cout << "\n";
    
    for(int i=1;i<=n;i++) h[i].clear();
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int t = 1;
    std::cin >> t;
    for(int i=1;i<=t;i++)
        solve();
    return 0;
}