比赛 ICPC复现(AI数据) 评测结果 AAAAAAA
题目名称 收益 最终得分 100
用户昵称 123 运行时间 1.616 s
代码语言 C++ 内存使用 37.03 MiB
提交时间 2026-05-26 20:52:28
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6e5 + 10;  // 注意边数 2*(n-1)
int n, m;
int idx[N], nxt[N], head[N], tot = 0;
ll a[N];
int cnt[N];  // 每个节点的人数
int parent[N];

void add(int x, int y) {
    idx[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}

int main() {
	freopen("shouyi.in","r",stdin);
	freopen("shouyi.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        int p;
        cin >> p;
        cnt[p]++;
    }

    // 非递归 DFS 求 parent 和后序顺序
    vector<int> post;
    stack<int> st;
    st.push(1);
    parent[1] = 0;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        post.push_back(u);
        for (int i = head[u]; i; i = nxt[i]) {
            int v = idx[i];
            if (v != parent[u]) {
                parent[v] = u;
                st.push(v);
            }
        }
    }
    reverse(post.begin(), post.end());  // 现在 post 是后序遍历顺序

    using PQ = priority_queue<ll, vector<ll>, greater<ll>>;
    vector<PQ> pq(n + 1);
    ll ans = 0;

    for (int u : post) {
        // 合并所有儿子的优先队列到 u
        for (int i = head[u]; i; i = nxt[i]) {
            int v = idx[i];
            if (v == parent[u]) continue;
            // 启发式合并:将小的并入大的
            if (pq[u].size() < pq[v].size()) {
                pq[u].swap(pq[v]);
            }
            while (!pq[v].empty()) {
                pq[u].push(pq[v].top());
                pq[v].pop();
            }
        }

        // 加入当前节点的物品(等价于插入 -a[u])
        if (pq[u].empty()) {
            pq[u].push(-a[u]);
        } else {
            ll val = pq[u].top();
            pq[u].pop();
            pq[u].push(val - a[u]);
        }

        // 结算当前节点的人,每人拿走当前最小的一个(负值即最大价值)
        while (cnt[u]-- && !pq[u].empty()) {
            ans -= pq[u].top();   // 减去负值 = 加上实际价值
            pq[u].pop();
        }
    }

    cout << ans << '\n';
    return 0;
}