The solution of「CF1665C Tree Infection」

· · 题解

\textup{CF1538C Number of Pairs}

\textup{Luogu} | \textup{CF} | \textup{Cnblog}

我要严肃开始喷这个题意了，怎么这么恶心。

哦对，参考了第一篇题解的做法其实是题意解释，但我觉得它有些地方没讲清楚。

\textup{Description}

给定有根树，对于每个节点，可以进行单点染色（下文统一叫这个）和传染操作。

传染操作定义为每秒钟自动将所有被感染节点要向其所有直接的子节点传播，一秒一个，使得其感染。

其中满足条件的节点都可以同时进行操作。

问整棵树都被感染的最小时间。

\textup{Solution}

知道题意后就没什么难的了，凭直觉做。

对于每个点，我们只需要关注其子节点的数量即可，这会直接影响一个点的传播能力。

令其为 siz_u，注意 siz 表示的不是子树的大小，而是直接的子节点的个数。

考虑对于一棵子树，若没有单点染色操作，需要时间为 siz_u - 1，并且受 u 被染色的时间影响。

首先是根节点，必须得被手动染色。

然后是对所有节点的 siz 进行排序，先把 siz = 0 的排掉，接着用一个最大堆维护我们操作的顺序。

这样我们就能每次处理最大的 siz，同时模拟即可。

所以二分在哪？

\textup{Code}

实现太差了，参考了一下第一篇题解的实现，结构上会有点像。

\textup{Submission Record}.

const int MAXN = 2e5 + 5;
int T, N, p;

int siz[MAXN], a[MAXN], tot;

void solve(){
    priority_queue<int> q;//维护剩余未被覆盖的子节点数
    int pos = 0;
    cin >> N;
    for( int i = 0; i <= N + 3; i ++ ) siz[i] = 0;
    for( int i = 2; i <= N; i ++ ) cin >> p, siz[p] ++;

    siz[0] = 1;//根要被手动染色
    sort( siz, siz + N + 1 );
    while( siz[pos] == 0 && pos <= N ) pos ++;//跳过为0的点
    for( int i = pos; i <= N; i ++ ){
        int now = siz[i] - ( i - pos ) - 1;//已经有i-pos秒的传播，然后自己是注射的
        if( now > 0 ) q.push( now );
    }
    int ans = N - pos + 1, tim = 0;
    //ans:计算总时间，先把前面要用的时间计进去 tim:后续的轮数
    while( !q.empty() && q.top() > tim ){
        tim ++;
        int now = q.top();
        q.pop();
        if( now - 1 > tim ) q.push( now - 1 );//如果还需要后续的操作
        ans ++;
    }//这里看起来没更新总动染色对吧，但是tim++会使得后面计算算进去。
    cout << ans << endl;
}

\textup{Last}

审核管理员辛苦了，如果您有什么看不懂、我太弱了所以讲错了的地方，请您在评论区指出或找我，我一定会解答并且修改本题解。

如果您觉得本文写的还不错，那可以留个赞吗?

谢谢你看到这里~