# Gym 101612H Hidden Supervisors（贪心+树的匹配）

## Hidden Supervisors

• Input file: hidden.in
• Output file: hidden.out
• Time limit: 3 seconds
• Memory limit: 512 megabytes

Helena works in a big company as a psychologist. Her task is to organize a team building game to
enhance social relations between employees. Each employee except the Big boss has a single supervisor.
So, employees of the company form a tree where each employee is a node, and the parent of that node is
their supervisor. The root of the tree is the Big boss.
A team building game requires teams of two people. Every team should consist of an employee and their
supervisor.
Helena asked every employee except the Big boss to send their supervisor ID. Some of them didn’t reply.
She is going to assign a fake supervisor to every employee that didn’t reply, so that she could arrange as
many teams as possible. And, of course, fake and real supervisors must form a tree.
Helena had a difficult, but a successful day organizing the event. Will you be able to assign fake
supervisors?

### Input

The first line of the input contains a single integer n — the number of employees in the company
(2 ≤ n ≤ 100 000).
The following line contains n − 1 integers p2, p3, . . . , pn, where pi is the supervisor of employee i (0 ≤ pi ≤ n). If employee i didn’t reply to Helena, pi equals zero, and she needs to assign a fake supervisor to that employee. The Big boss has the number 1.
It’s possible to assign a fake supervisor to each employee that didn’t reply to Helena so that all employees
will form a tree having the Big boss as a root.

### Output

In the first line output a single integer m — the maximum possible number of arranged teams.
The next line should contain supervisors: n−1 integers, i-th of which denoting the supervisor of employee
i + 1 (either fake or real). Of course, all real supervisors should be preserved, and employees must form
a tree. It should be possible to arrange m teams using specified supervisors.

### 链接

https://cn.vjudge.net/problem/Gym-101612H

### 代码

StatusAccepted
Time108ms
Memory10736kB
Length2256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100010;
int n, fa[maxn], degree[maxn], match[maxn], ans, tot;

struct Node // 以当前节点为根节点的未匹配的子节点
{
int rt, size;
vector <int> unmatch;
bool operator < (const Node & r) const
{
return size > r.size;
}
}node[maxn];

vector <int> E[maxn], unmatch, V;

void dfs(int u)
{
match[u] = 0;
for (int i = 0; i < E[u].size(); ++i)
{
int v = E[u][i];
dfs(v);
if (!match[u] && !match[v])
{
match[u] = v;
match[v] = u;
++ans;
}
if (!match[v]) // 未匹配
unmatch.push_back(v);
}
}

int main()
{
freopen("hidden.in", "r", stdin);
freopen("hidden.out", "w", stdout);
scanf("%d", &n);
for (int i = 2; i <= n; ++i)
{
scanf("%d", fa + i);
if (fa[i])
{
++degree[i];
E[fa[i]].push_back(i);
}
}
ans = tot = 0;
V.clear();
for (int i = 1; i <= n; ++i)
{
if (degree[i] == 0)
{
unmatch.clear();
dfs(i);
if (i == 1 || match[i]) // 当前节点为1或者根节点已匹配
{
fa[i] = 1;
for (int j = 0; j < unmatch.size(); ++j)
V.push_back(unmatch[j]);
if (i == 1 && !match[i]) // 1未匹配
V.push_back(i);
}
else // 根节点未匹配，保存信息
{
node[tot].rt = i;
node[tot].size = unmatch.size();
node[tot++].unmatch = unmatch;
}
}
}
sort(node, node + tot); // 从大到小贪心
for (int i = 0; i < tot; ++i)
{
int x = node[i].rt;
if (V.size())
{
++ans;
int u = V.back();
fa[x] = u;
V.pop_back();
}
else
{
fa[x] = 1;
V.push_back(x);
}
for (int j = 0; j < node[i].size; ++j)
V.push_back(node[i].unmatch[j]);
}
printf("%d\n", ans);
printf("%d", fa[2]);
for (int i = 3; i <= n; ++i)
printf(" %d", fa[i]);
printf("\n");
return 0;
}

The end.
2018-08-17 星期五