BAPC 2019 A. Appeal to the Audience 贪心 + DFS

╰半夏微凉° 2023-07-18 04:48 5阅读 0赞

题目链接：https://nanti.jisuanke.com/t/44317  
题意：给你一棵树和k个值，要把这k个值放在k个叶子结点上，而对每个非叶子结点来说  
它的值为儿子结点的最大值，求除了根节点外所有结点的最大权值和  
思路：无疑是贪心着放，首先选取深度大的点放权值大的。所以我们先统计一下每个点的深度  
用优先队列来维护深度最大的，每次将这条链标记一下，这样就能得到每个点的实际影响权值的深度

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define fi first
    #define se second
    #define ls rt << 1
    #define rs rt << 1|1
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    #define pll pair<ll, ll>
    #define pii pair<int, int>
    #define ull unsigned long long
    #define pdd pair<double, double>
    const int mod = 998244353;
    const int maxn = 3e5 + 10;
    const int inf = 0x3f3f3f3f;
    vector<int> e[maxn], g[maxn];
    priority_queue<pii > q;
    priority_queue<int> q1;
    int a[maxn], f[maxn];
    int L, R;
    
    void dfs(int u, int fa, int d)
    {
        for(auto v : e[u])
        {
            dfs(v, u, d + 1);
        }
        q.push({d, u});
    }
    void slove(int u, int fa, int d)
    {
        if(f[u])
        {
            q1.push(d);
            return;
        }
        f[u] = 1;
        for(auto v : g[u])
        {
            slove(v, u, d + 1);
        }
    }
    
    int main()
    {
        int n, k;
        scanf("%d%d", &n, &k);
        L = 1, R = k;
        for(int i = 1; i <= k; ++i) scanf("%d", &a[i]);
        sort(a + 1, a + k + 1);
        for(int i = 1; i < n; ++i)
        {
            int x;
            scanf("%d", &x);
            e[x].push_back(i);
            g[i].push_back(x);
        }
        dfs(0, -1, 0);
        f[0] = 1;
        while(!q.empty())
        {
            auto it = q.top();
            q.pop();
            slove(it.se, -1, 0);
        }
        ll sum = 0;
        while(q1.size() > 0)
        {
            int tmp = q1.top();
            q1.pop();
            sum += 1ll * tmp * a[R--];
        }
        for(int i = 1; i <= R; ++i) sum += a[i];
        printf("%lld\n", sum);
        return 0;
    }