HDU 5242 上海邀請賽：樹上優先隊列貪心取值

題目

根為 1 的樹，每點有權值。從根出發走到葉子，沿途拿取點權值（每點只能拿一次）。進行 k 次遊戲，每次從根重新開始。求最大總權值。

貪心 + 優先隊列

每次遊戲相當於選一條根到葉路徑。為最大化總和，應優先選擇「單位深度權值密度」高的路徑。實際上可反向思考：從所有葉子開始，將路徑壓入優先隊列，按（深度、權值）排序。每次取出隊首路徑，拿取其端點權值，若端點非根則將路徑縮短一步（移至父節點）重新入隊。重複 k 次。預處理深度時利用記憶化避免重複計算。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int parent[MAXN], depth[MAXN];
long long val[MAXN];
bool vis[MAXN];

struct Path {
    int u; long long sum; int dep;
    bool operator<(const Path& o) const {
        return dep < o.dep || (dep == o.dep && sum < o.sum);
    }
};

int getDepth(int u) {
    if (depth[u]) return depth[u];
    if (u == 1) return depth[u] = 1;
    return depth[u] = getDepth(parent[u]) + 1;
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int n, k; scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i++) scanf("%lld", &val[i]);
        memset(parent, 0, sizeof(parent));
        memset(vis, 0, sizeof(vis));
        memset(depth, 0, sizeof(depth));
        for (int i = 1; i < n; i++) {
            int x, y; scanf("%d%d", &x, &y);
            parent[y] = x; vis[x] = true;
        }
        priority_queue pq;
        for (int i = 1; i <= n; i++)
            if (!vis[i]) { // 葉子
                int d = getDepth(i);
                pq.push({i, val[i], d});
            }
        long long ans = 0;
        int played = 0;
        while (!pq.empty() && played < k) {
            Path cur = pq.top(); pq.pop();
            if (cur.u == 1) { // 到達根
                ans += cur.sum;
                played++;
            } else {
                int p = parent[cur.u];
                cur.sum += val[p];
                cur.u = p;
                cur.dep = getDepth(p);
                pq.push(cur);
            }
        }
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}