[C++知识库]C. Tree Infection

https://codeforces.com/contest/1665/problem/C

input

5
7
1 1 1 2 2 4
5
5 5 1 4
2
1
3
3 1
6
1 1 1 1 1

output

4
4
2
3
4

题意
给定一颗树，循环 多次 先后 进行以下两步操作，询问最短花费多少时间使得树上每个节点都被染色

1. 在每个父节点中，若其某个儿子倘若被染色了，则可以指定其另外 一个 儿子染色 （称为被动染色）
2. 选择一个节点进行染色 （称为主动染色）

ps：假定一个父节点有四个儿子节点，且其中两个已经被染色，则经过一轮操作 $1$ ，最后变成三个儿子节点被染色，以及儿子节点并不会传染给父节点

思路

首先明确一点：儿子节点并不会传染给父节点，反过来父节点也不会传染给儿子，

如下图：
对于一堆有 $t$ 个相同父节点的节点，假定一开始其中一个被染色并且我们不主动去染色，仅凭操作一它将会活动时间为 $t?1$ 便将这堆节点给染色完，之后便没有变化，且父节点没有变化

所以看出来每个父节点所对应的 子节点堆 都需要手动用操作 $2$ 去染色

我们先将每个子节点堆取出来，然后根据贪心的思想，主动染色每次只能只能对一个点进行染色，而被动染色会发生在每个被染色过的堆中，所以最优的策略应该是对每个堆都 蜻蜓点水 ，让被动染色尽可能去消耗。但是主动染色是有个先后的过程，先染色的堆自然会被被动染色更多的点，而后染色的堆则会相对少一些

所以可以sort一下，先将数量大的堆先进行主动染色其中一个点，然后靠被动染色逐渐感染去消耗更多。

（如下图）
每列的高度表示每个堆的大小，绿色表示会被被动染色染色的过程（ps其中包含一个主动染色的块）

当我们将每个堆都染过一遍后，还有一些堆还剩余的怎么办？即上图中空白的块

因为我们知道染色的先后时间，所以可以计算出每个堆所剩多少个未染色的方块

这时候我们得用主动染色去帮助未完成的堆
因为每个情况比较复杂，以及题目所求的是最短时间，我这里便想到使用二分

即二分枚举剩下还会进行的时间

如何 $check$ 枚举的 $mid$ 是否成立 ？
即：$mid$ 代表还会经过的时间，则表示可以主动染色 $mid$ 个位置 ，且被动染色也会在每一堆中消耗 $mid$ 个，所以每一堆剩下的数量减去 $mid＞0$ ，则就表示我需要用主动染色去凑剩下的部分，所以对于每个堆统计一下需要主动染色的数量总和，再与 $mid$ 比较即可

AC代码
记得根节点也需要我们自己去染色

#include <algorithm>
#include <bits/stdc++.h>
#include <functional>
#include <vector>
#define endl '\n'
#define AC return 0;
using namespace std;
//#define ll long long
#define int long long

vector<int>v[200005];
vector<int>cnt;

void dfs(int p)
{
    if(v[p].size())
        cnt.push_back(v[p].size());
    for(auto i : v[p])
        dfs(i);

}

bool jud(int mid)
{
    int ti = mid;
    for(auto i : cnt)
    {
        if(i > mid)
            ti -= i - mid;
    }
    return ti >= 0;

}

void slove()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        v[i].clear();
    cnt.clear();
    for(int i = 2; i <= n; i++)
    {
        int x;
        cin >> x;
        v[x].push_back(i);
    }    
    dfs(1);
    cnt.push_back(1);
    int sum = cnt.size();
    int k = 0;
    int ti = sum;
    sort(cnt.begin(),cnt.end(),greater<>());
    for(auto &i : cnt)
    {   
        i = max((int)0,i - ti);
        ti--;
    }
    // cout << sum << endl;
    int l = 0,r = 1e12;
    int ans;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(jud(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << sum + ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin >> T; while(T--)
    slove();
    AC
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖