题目描述

链接：https://ac.nowcoder.com/acm/contest/103948/F 来源：牛客网

小红拿到了一棵由 n 个节点组成的树，她已经把所有节点都染成了红色。这时，小紫准备将 k 个节点染成紫色，使得最大红色连通块的大小尽可能小。你能帮帮她吗？

对于树上的两个点，如果它们均为红色且相连，则称他们位于同一个红色连通块里。特别地，一个单独的点也构成一个红色连通块。连通块的大小即为连通块中节点的数量。

解题思路

第一次写题解，思路或是描述有什么不对的或是不恰当的，还望海涵指正，谢谢。

首先题目中要求最大的连通块尽可能小，对于这种求最大的什么尽可能小和最小的什么尽可能大的问题，我们很容易想到使用二分答案。

具体怎么去二分呢？由于连通块的大小越大，我们需要染成紫色的节点数就越小，具有单调性，因此我们可以对连通块的大小进行二分，去求出在满足当前连通块大小前提下，需要染几个紫色节点，假如规定当前的连通块大小为 $mid,check(mid)$ 为满足以当前连通块大小的连通块数目的前提下，所需要染的紫色节点数。

//二分连通块大小
if(check(mid))>k)
//如果染色数量大于k，就放大连通块，让染色数变小
	l=mid;
else
//如果染色数量小于等于k,就尽可能缩小连通块，求出最小的满足的连通块
	r=mid;

但题目中说的是恰好染 $k$ 个节点，为什么二分的时候要求出尽可能小于 $k$ 个呢，可以思考一下，如果当前连通块的大小所需要的染成紫色的节点数为 $m$ 个，那么剩余的 $m-k$ 个染色次数可以用在剩余的红色节点上，那么会使得最大的连通块的大小不会超过mid。

那么具体需要如何去实现呢？我们可以定义 $cnt[i]$ 为以结点 $i$ 为根节点的连通块(包含根节点)的大小,如果 $cnt[i]>mid$ ,此时cnt[i]=mid+1,说明需要将当前节点染色，这样就会将当下大于mid的连通块大小 $<=mid$ ,此时让注意此时要让cnt[i]=0，因为当前点以为紫色，需要消除他对后续红色连通块统计时的贡献，这个过程可以使用dfs去具体实现

int need=0;
vector<int> cnt(n+1,0);
auto dfs=[&](auto&& dfs,int son,int fa)->void{
	cnt[son]=1;
    for(auto& grandson : adj[son])
    {
    	if(grandson==fa)continue;
        dfs(dfs,grandson,son);
        cnt[son]+=cnt[grandson];
    }
    if(cnt[son]>mid)
    {
    	need++;
        cnt[son]=0;
    }
}

具体代码：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int mod = 1e9 + 7;
/*码字有神
遇事不决，可问春风，春风不语，即随本心
从小丘西行百二十步，隔篁竹，闻水声，如鸣佩环
晋太元中，武陵人捕鱼为业，缘溪行，忘路之远近，忽逢桃花林
*/
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<vector<int>> adj(n + 1);//创立邻接表
    for (int i = 1; i < n; i++)//用邻接表建树
    {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    auto check = [&](int mid) -> int
    {
        int need = 0;
        vector<int> cnt(n + 1, 0);
        auto dfs = [&](auto &&dfs, int son, int fa) -> void//遍历
        {
            cnt[son] = 1;
            for (auto &grandson : adj[son])
            {
                if (grandson == fa)
                    continue;
                dfs(dfs, grandson, son);
                cnt[son] += cnt[grandson];
            }
            if (cnt[son] > mid)
            {
                need++;
                cnt[son] = 0;//消除对后续算连通块时的贡献
            }
        };
        dfs(dfs, 1, 0);
        // cout << need;
        return need;
    };
    int l = -1, r = (int)1e5 + 10;
    while (l + 1 < r)//清纯可爱的开区间二分
    {
        int mid = (l + r) / 2;
        if (check(mid) > k)
            l = mid;
        else
            r = mid;
    }
    cout << r<<endl;
}
signed main()
{
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}
/*
使得最大值最小，最小值最大......:二分答案
二分最大值：if(check(mid)) r = mid,看r能不能更小
*/

有关树的这种题的思考

这一题的题解我是在看了牛客官方的题解视频后，才写出来的，理解的可能有不对的地方，还望海涵。

下面说一说自我的感受和反思吧，不喜欢的话，还望多多包容。

其实之前写树的题包括在学树的数据结构的时候，我一直有个疑惑，就是怎么从给定的若干的节点对应的边中去把这颗树给建立出来，建立出来后树的根节点是那个节点呢。后来在写题时看到有人用邻接表去建树，但我不知道怎么去对邻接表所建立树进行dfs操作，也可能是我刷的树的题太少了，但接连几场的牛客周赛补题下来，我发现了在对邻接表构建的树进行dfs时的规律或者说是模板吧，才渐渐地解决了我心中的疑惑，我把这段优美的代码写下来。

//一段优美的代码
vector<vector<int>> adj(n+1);
for(int i=0;i<n;i++)//建树
{
	int u,v;
    cin>>u>>v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
}
//遍历
auto dfs=[&](auto&& dfs,int son,int fa)->void
{
	/*
    一些操作
    */
    for(auto& grandson : adj[son])
    {
    	if(grandson==fa)continue;
        dfs(dfs,grandson,son);
        /*一些操作*/
    }
    /*
    一些操作
    */
};
dfs(dfs,1,0);/*假定1为根节点开始遍历，因为树中的每一个节点
都可以充当根节点，把它提起来就是一颗树了*/

2025.3.18更新这篇博客，今天在刷题时碰到了树的层序遍历，由于本期博客与树相关，所以就把新学到的关于邻接表构建的树的遍历方法写在这里，供大家参考指正。今天写的这道题是需要求出树的深度和最后一层的节点值，但我开始动手写的时候，求出来的层数总是十分的大，换句话说就是节点的数量，一时间很难想到怎么去层序遍历，后来想了一下每一个bfs遍历阶段中队列中的状态，我幡然醒悟。

如果第二层遍历完成，那么此时队列中的第一层元素已全部出队，此时队列中的元素只有第二层的元素，同理如果第三层遍历完成，那么此时第二层元素已全部出队，此时队列中的元素只有第三层的元素，也就是我们可以通过出队当前层的元素数量个元素来表示当前层已遍历完毕，层数加一，到最后即可求出层数。同时为了防止向父节点遍历，要设置一个vis数组，记录被访问过的节点

下面来看一下这段优美的代码。

vector<vector<int>> adj(n+1);//构建邻接表
for(int i=0;i<n;i++)
{
	int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}//邻接表建树

auto bfs=[&](int root)->int{
	queue<int> q;
    int level=0;
    q.push(root);
    //vector<int> level_node;
    //记录每一层的节点
    vector<int> vis(n+1,0);
    //标记已访问的节点，防止子节点向其父节点访问
    vis[root]=1;
    while(!q.empty())
    {
    	int level_size=q.size();
        //记录每一层的数量，作为层数增加的依据
        level++;
        for(int i=0;i<level_size;i++)
        {
        	int fa=q.front();
            //level_node.push_back(fa);
            q.pop();
            for(auto& son : adj[fa])
            {
            	if(!vis[son])
                {
                	q.push(son);
                    vis[son]=1;
                }
            }
        }
        //for(int k :  level_node)
        //{
        //	cout<<k<<' ';
        //}
        //cout<<endl;
    }
    return level;
};

小紫的树上染色引发的思考

题目描述

解题思路

具体代码：

有关树的这种题的思考