自动搬运

查看原文

来自洛谷，原作者为

	command_block 众水皆昂首，饮月唯我一。

搬运于2025-08-24 22:25:59，当前版本为作者最后更新于2021-10-20 20:59:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

鱼大博客长长长，暂且没看，自己做出来了，感动（

题意 ： 给定一个 $n$ 个点的内向森林，其中 $1$ 号点为某个树的根。

你需要将这个森林连成一棵以 $1$ 为根的有根树，并使得最终树（对应的无根树）的最大匹配尽可能大。

$n\leq 10^5$ ，时限$\texttt{3s}$。

最终方案显然是除了 $1$ 外每个根连出一条边。

• 树上最大匹配的贪心 ：从深往浅考虑，每个点若能匹配父亲则匹配。

  注意，若占用根的最大匹配和不占根的最大匹配大小相同，贪心会得出不占根的方案。

我们考虑逐棵树考虑根的连边情况，且要求新的小树 $T'$ 必须连接到 $1$ 所在的大树 $T$ 上。

假设我们已经确定了一种树的排列，如何构造最优的方案。（显然每种方案都能对应一种排列）

记准备接到大树 $T$ 上的小树为 $T'$。

记 $\max(T)$ 为 $T$ 的最大匹配。由于只加了一条边，连接后最大匹配的上界显然为 $\max(T)+\max(T')+1$ 。

观察连接之后贪心的形为。由于贪心从浅到深考虑，$T'$ 内部的匹配不会变化。

记 $T'$ 的根为 $t$ 。

• $\max(T')$ 含 $t$

  此时新边的深端（$T'$ 的根）已经被占用，故新边一定不会被选中。$T,T'$ 原有的匹配均保持。

• $\max(T')$ 不含 $t$

  容易想到，若 $T$ 中存在非匹配点，则将 $t$ 与之连接，能多出一个匹配边。这已经达到上界。

  否则，若 $T$ 中不存在非匹配点，考虑点集 $T\cup\{t\}$ ，它们之中的匹配才可能变化。但现在满匹配仅多加一个点，显然匹配不可能增大。

综上，我们证明了 ：

加入 $T'$ 时，若 $T'$ 的根为非匹配点，且 $T$ 中存在非匹配点 $v$ ，则连接 $(t,v)$ 并使匹配加一。

若条件不满足，匹配不可能增大，为避免影响匹配情况（不便考虑），直接令 $t$ 与 $1$ 相连，不难发现此时可以认为贪心算法不会改动匹配。

• 观察如上算法的行为：

  记顺序为 $T_{1\sim m}$ ，其中 $T_1$ 肯定是 $1$ 所在的树。

  $T_1$ 能提供若干非匹配点（可能包括根）。

  对于 $T_2$ ，若根非匹配，选择一个非匹配点连接。若根已匹配，或找不到非匹配点，则弃疗，直接连向 $1$ 。不要忘记添加新的非匹配点。

接下来进一步考虑：何种顺序才是最优的？

我们的目标是尽量让更多的树加入时能新增匹配，这和现存的非匹配点有关。不难想到经典的贪心：根已匹配的树无要求，先直接圈接入，接下来在根非匹配的树中，让非匹配点更多的树打头阵。

#include<algorithm>
#include<cstdio>
#include<vector>
#define MaxN 100500 
using namespace std;
vector<int> p[MaxN],g[MaxN];
int st[MaxN],tn;
bool vis[MaxN];
void dfs(int u,int fa)
{
	for (int i=0;i<g[u].size();i++)dfs(g[u][i],u);
	if (!vis[u]&&!vis[fa])vis[u]=vis[fa]=1;
	if (!vis[u])st[++tn]=u;
}
int a[MaxN],fa[MaxN],nrt,w[MaxN];
bool cmp(int A,int B){return w[A]>w[B];}
int main()
{
  int n;scanf("%d",&n);
  for (int i=2;i<=n;i++){
  	scanf("%d",&fa[i]);
  	if (fa[i])g[fa[i]].push_back(i);
  }
  vis[0]=1;
  int ans=0;
  for (int u=1;u<=n;u++)if (!fa[u]){
    	tn=0;
    	dfs(u,0);
    	ans+=tn;
    	for (int i=1;i<=tn;i++)p[u].push_back(st[i]);
    	w[u]=(vis[u] ? n+1 : p[u].size());
    	a[++nrt]=u;
    }
  ans=(n-ans)/2;
  w[1]=n+2;
  sort(a+1,a+n+1,cmp);
  tn=0;
  for (int i=0;i<p[1].size();i++)st[++tn]=p[1][i];
  for (int k=2;k<=n;k++){
  	int u=a[k];
  	while(tn&&vis[st[tn]])tn--;
  	if (!vis[u]&&tn){vis[u]=1;vis[fa[u]=st[tn]]=1;ans++;}
  	else fa[u]=1;
  	for (int i=0;i<p[u].size();i++)st[++tn]=p[u][i];
  }
  printf("%d\n",ans);
  for (int i=2;i<=n;i++)printf("%d ",fa[i]);
	return 0;
}