予鈴

競プロとか備忘録とか…

B - PackDrop

葉から根に向かって最小値を更新していき、dfsで解くことができます。
シンプルで好きです。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
#define mp make_pair
#define INF 1e9
int ans=0;
vector<vector<int>>edge(1001,vector<int>());
vector<int>cost(1001,INF);
void dfs(int vertex){
    if(edge[vertex].size()==0)return;
    rep(i,edge[vertex].size()){
        int to = edge[vertex][i];
        ans+=cost[to]-cost[vertex];
        dfs(to);
    }
    return;
}
int main(){
    int n,m; cin>>n>>m;
    vector<int>par(n+1);
    using pii =  pair<int, int>;
    rep(i,n-1){
        int v; cin>>v;
        edge[v].push_back(i+1);
        par[i+1]=v;
    }
    vector<int>leaf;
    rep(i,m){
        int v,b;  cin>>v>>b;
        cost[v]=b;
        leaf.push_back(v);
    }
    rep(i,leaf.size()){
        int v=leaf[i];
        while(v!=0){
            cost[par[v]]=min(cost[par[v]],cost[v]);
            v=par[v];
        }
    }
    ans+=(int)edge[0].size()*cost[0];
    
    dfs(0);
    cout<<ans<<endl;
}