[LibreOJ β Round #3] 绯色 IOI（抵达）

一、题目

点此看题

二、解法

首先考虑任意两个不同的城市庇护所不同意味着什么。我首先想出来一个 \(\tt naive\) 的结论：每个叶子的庇护所一定是它的父亲，所以有解的条件是每个非叶节点至多连接一个叶子。

要让结论升级才能做题，我们考虑叶节点父亲的庇护所一定是他自己，那么这两个节点的匹配方案是唯一确定的，我们把这两个节点同时删去之后得到一个新树，递归操作直到树为空即可，所以如果有解匹配方案也只有一种。

这种匹配方案是好求的，我们用队列模拟一下删叶子的过程即可。这个唯一的匹配方案就可以把原限制转化成若干个偏序关系，我们把偏序关系建成拓扑图，依次考虑权值 \(1\rightarrow n\) 赋值，维护一个关于编号的小根堆，每次把堆顶删去即可。

三、总结

观察性质，可以从一些简单结论入手，然后再考虑上升结论。

树的匹配问题可以从叶子着手考虑，因为叶子处的匹配可能最简单。

#include 
#include 
#include 
using namespace std;
const int M = 500005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,cnt,a[M],d[M],ans[M];vector g1[M],g2[M];
void link(int u,int v)
{
	if(u==v) return ;
	g2[u].push_back(v);d[v]++;
}
void tpsort()
{
	priority_queue,greater >q;
	for(int i=1;i<=n;i++)
		if(d[i]==0) q.push(i);
	while(!q.empty())
	{
		int u=q.top();q.pop();
		ans[++m]=u;
		for(int i=0;i q;
	for(int i=1;i<=n;i++)
		if(a[i]==1) q.push(i);
	while(!q.empty())
	{
		int u=q.front(),t=0;q.pop();
		for(int i=0;i0)//his shelter
				t=g1[u][i],a[g1[u][i]]=0;
		if(!t) continue;
		//build some edge
		for(int i=0;i