牛客小白月赛64 D-Karashi的树 I(dfs)

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

1. 每个点的价值是它到根节点的路径上所有节点的所有点权和（包括它自己）

2. 点数其实也就是从根节点数 这棵子树有多少个子节点，这就是出现次数

3. 显而易见所有点的权值都可以随便变化，没有规定变换次数，所以我们可以随意变换成我们想要的样子

4. 所以直接排序依次把子树多的点安排在前面

5. 答案就是排序后的价值和排序后的当前节点下子树的总节点数量相乘

输入 
9
3 5 3 4 6 1 5 1 6
1 2 2 2 1 6 6 8
输出
120

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=500200,M=2002;
//vector<LL> v[N];
//unordered_map<LL,LL> a[N];
//priority_queue<LL> pq;
//priority_queue<LL,vector<LL>,greater<LL>> pq2;
LL n,a[N],sum[N];
vector<LL> v[N];
void dfs(LL u,LL fa)
{
    sum[u]=1;
    for(int i=0;i<v[u].size();i++)
    {
        if(v[u][i]==fa) continue;
        dfs(v[u][i],u);
        sum[u]+=sum[v[u][i]];
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+1+n);
        for(int i=2;i<=n;i++)
        {
            LL x;
            cin>>x;
            v[x].push_back(i);
        }
        dfs(1,0);
        sort(sum+1,sum+1+n);
        LL ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=(LL)sum[i]*a[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}