题解 【P7026 [NWRRC2017]Hidden Supervisors】
command_block
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$ 。不要忘记添加新的非匹配点。
接下来进一步考虑：何种顺序才是最优的？
我们的目标是尽量让更多的树加入时能新增匹配，这和现存的非匹配点有关。不难想到经典的贪心：根已匹配的树无要求，先直接圈接入，接下来在根非匹配的树中，让非匹配点更多的树打头阵。
```cpp
#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;
}
```