「CometOJ2028」迫真小游戏

题意：

由于需要保证字典序最小，只需要每次从当前可以选择的还没有部署干员的节点中选择编号最小的。记当前没有被选择的所有点的 $a[]$ 的最小值为 $t$，可以用一个 $\texttt{multiset}$ 维护，并且 $t$ 不会减小。受到限制而不能选择的点是深度大于 $t$ 的所有点，每次 $t$ 增大时把从不能选择变成可以选择的点(用一个 $\texttt{vector}$ 维护每个深度的点)加入堆(优先队列)中，每次取最小值即可得到答案。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
int n,head[501010],cnt,ans[501010];
int dep[501010],a[501010],num,depth;
struct node
{
	int next;
	int to;
}e[1001010];
vector<int> s[501010];
priority_queue< int,vector<int>,greater<int> > q;
multiset<int> t;
void add(int from,int to)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	head[from]=cnt;
}
void dfs(int u,int fa)
{
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa)
			continue;
		dep[v]=dep[u]+1;
		dfs(v,u);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		t.insert(a[i]);
	}
	dep[1]=1;
	dfs(1,0);
	for(int i=1;i<=n;i++)
		s[dep[i]].push_back(i);
	for(int _=1;_<=n;_++)
	{
		int p=*t.begin();//取出最小a[i]
		while(depth<p)
		{
			depth++;
			for(int i=0;i<(int)s[depth].size();i++)
				q.push(s[depth][i]);
		}
		int u=q.top();
		ans[++num]=u;
		q.pop();
		t.erase(t.find(a[u]));
	}
	for(int i=1;i<=num;i++)
		printf("%d ",ans[i]);
	return 0;
}