【2023NOI模拟赛22】商店 做题记录

给定一个以 $0$ 为根的 $n$ 个点的树，编号在 $[0,n-1]$ 范围内，第 $i$ 个点上的权值为 $i$ 的东西。

有 $m$ 个客人前来买东西，第 $i$ 个客人只能买 $ct_i$ 子树点上的东西，且一个客人只能买一个东西，一个东西只能被卖给一个客人。

你需要最大化卖出的东西的权值和。

$1\le n,m\le 3\times 10^6$，时间复杂度要求低于 $O(n\log n)$。

首先有个显然的贪心，客人按照 $ct_i$ 的深度从大到小依次选择子树内权值最大的东西买走。

这等价于按照权值从大到小考虑每个点，选择所有能买它的客人中 $ct_i$ 深度最大的那一位被他买走。

并查集维护即可，但是我不会并查集。

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

inline int read()
{
	int c=0,s=0;
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
	return s;
}

const int S=3000005;

int n,m,fat[S],cnt[S];
int fa[S];

int fnd(int u){return fa[u]==u?u:fa[u]=fnd(fa[u]);}

int main()
{
	freopen("shop.in","r",stdin);
	freopen("shop.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n-1;i++) fat[i]=read();
	for(int i=1;i<=m;i++) cnt[read()]++;
	for(int i=0;i<=n-1;i++) fa[i]=i;
	long long ans=0;
	for(int i=n-1;i>=0;i--)
	{
		int u=i;
		while(fnd(u)!=0&&cnt[fnd(u)]==0)
		{
			int ru=fnd(u);
			fa[ru]=fat[ru];
		}
		int ru=fnd(u);
		if(cnt[ru]>0)
		{
			ans+=i;
			if(--cnt[ru]==0) fa[ru]=fnd(fat[ru]);
		}
	}
	printf("%lld\n",ans);
	return 0;
}