背景：

原题链接
我考场上15分钟左右最出来的，写篇题解纪念一下。

思路：

由于保证$f_i<i$，所以编号越大的节点一定深度越大，子节点越少。所以，从节点$n$开始遍历，如果该节点有子节点，那么将该节点所有子节点的染色代价加起来，与该节点的染色代价作比较，取最小值并更新到$c$数组，而这个值就是将该节点以及它的所有子节点到根节点$1$的路径染色的最小代价，一直遍历到根节点$1$，而$c[1]$就是最小代价了。

数据范围：

由于ACGO上摘的数据范围不完整，这里提供完整的数据范围：

代码：

#include <iostream>
#include <vector>
using namespace std;
vector<int>v[100010];
long long c[100010];
int main(){
    int n;
    cin>>n;
    for (int i=2;i<=n;i++){//从节点2~n
        int f;
        cin>>f;
        v[f].push_back(i);//节点i的子节点
    }
    for (int i=1;i<=n;i++){
        cin>>c[i];
    }
    for (int i=n;i>=1;i--){
        if (v[i].size()){//如果节点i有子节点
            long long cnt=0;
            for (auto k:v[i]){
                cnt+=c[k];
            }//统计该节点所有子节点的染色代价和
            c[i]=min(c[i],cnt);//取最小值更新
        }
    }
    cout<<c[1];//输出c[1]
    return 0;
}

结语：

希望对大家学习OI有帮助！