2023牛客寒假算法基础集训营2-D

https://ac.nowcoder.com/acm/contest/46810/D

DFS 深搜代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int n,fa[200010];
vector<int> g[200010];
ll v[200010],dep[200010];
void dfs(int now,int d)
{
    dep[now]=d;
    for(auto to:g[now])
    {
        dfs(to,d+1);
    }
}
int main()
{
    cin>>n;
    for(int i=2; i<=n; i++)
    {
        scanf("%d",&fa[i]);
        g[fa[i]].push_back(i);
    }
    for(int i=1; i<=n; i++) scanf("%lld",&v[i]);
    dfs(1,1);
    sort(v+1,v+1+n);
    sort(dep+1,dep+1+n);
    ll ans=0;
    for(int i=1; i<=n; i++)
    {
        ans=ans+dep[i]*v[i];
    }
    printf("%lld\n",ans);
    return 0;
}