P7130 「RdOI R1」平衡常数(balance) 题解

ni_ju_ge · 2025-07-16 09:06:42 · 题解

题目传送门

思路

考虑当前已做完 x 子树内的选择，到达 x 时怎么操作。下面将满足一条件称为“平衡”。

发现删除原本平衡的子树内任意一个选取的点，不会破坏平衡。那么为了最大化权值和，若选取 x 会破坏平衡，可以贪心地删去选取点中的最小点，再将 x 选上以增大权值和（如果这样会使权值和变小，则不进行此操作）。

可以使用小根堆记录最小的权值，到 x 时合并子节点的小根堆再进行操作。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int x,y,n;
long long ans,a[N];
struct node {
    int siz,qu;
    vector<int> ch;
} tr[N];
vector<int> ed[N];
struct xgd {
    int l,r;
    long long dat;
    int key;
} v[N];
int root[N],cnt;
int make(int val) {
    v[++cnt].dat=val;
    v[cnt].key=rand();
    return cnt;
}
int merge(int r1,int r2) {//堆合并
    if(!r1||!r2) return r1+r2;
    if(v[r1].dat>=v[r2].dat) {
        if(v[r1].key<=v[r2].key) v[r2].l=merge(r1,v[r2].l);
        else v[r2].r=merge(r1,v[r2].r);
        return r2;
    } else {
        if(v[r2].key<=v[r1].key) v[r1].l=merge(v[r1].l,r2);
        else v[r1].r=merge(v[r1].r,r2);
        return r1;
    }
}
void take(int loc,int val) {
    root[loc]=merge(root[loc],make(val));
}
void del(int loc) {
    root[loc]=merge(v[root[loc]].l,v[root[loc]].r);
}
void dfs1(int pos) {//建树
    tr[pos].siz=1;
    for(int i=0;i<ed[pos].size();i++) {
        int nxt=ed[pos][i];
        if(!tr[nxt].siz) {
            dfs1(nxt);
            tr[pos].ch.push_back(nxt);
            tr[pos].siz+=tr[nxt].siz;
        }
    }
}
void dfs2(int pos) {//贪心求解
    for(int i=0;i<tr[pos].ch.size();i++) {
        int nxt=tr[pos].ch[i];
        dfs2(nxt);
        tr[pos].qu+=tr[nxt].qu;
        root[pos]=merge(root[pos],root[nxt]);
    }
    if(tr[pos].siz!=1) {//注意叶子结点一定不能选
        if(tr[pos].qu>=tr[pos].siz/2&&a[pos]>v[root[pos]].dat) {
            del(pos);//删去最小值
            take(pos,a[pos]);
        }
        if(tr[pos].qu<tr[pos].siz/2) {
            take(pos,a[pos]);
            tr[pos].qu++;
        }
    }
}
void dfs3(int pos) {//计算权值和
    if(!pos) return;
    ans+=v[pos].dat;
    dfs3(v[pos].l);
    dfs3(v[pos].r);
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++) {
        cin>>x>>y;
        ed[x].push_back(y);
        ed[y].push_back(x);
    }
    dfs1(1);
    dfs2(1);
    dfs3(root[1]);
    cout<<ans;
}