自动搬运

查看原文

来自洛谷，原作者为

	ni_ju_ge 也该留下点什么了

搬运于2025-08-24 22:26:55，当前版本为作者最后更新于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;
}