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; }