NC572 题解 | #连通块#

题意分析

• 给你一棵树，需要我们将这棵树划分为k个联通块，同时每个联通块的节点的权值的和都要大于等于给定的值，问是否可以达到目的。

思路分析

• 我们观察得到，为了确保是联通块，而且达到贪心的目的，我们应该从树的叶子节点往上面进行扩展。如果某一个节点和他的子树可以构成一个满足题目条件的联通块。那么我们就将这棵树和他的结点的权值都置为0.继续向上进行扩展。这是一个树形DP的思想。当然，也可以用BFS进行处理。

• 如下图

解法一 DFS(DP）

• 根据上面的分析，我们可以很好的写出这个DP函数，首先，从根节点开始进入，然后，处理字节点，同时判断此时的子节点是否可以构成一个满足条件的联通块。可以就将权值都置为0.

• 代码如下

  • 需要遍历所有的结点以及他们的连边。所以，时间复杂度为
  • 需要存储所有的边的情况以及权值情况。所以空间复杂度为

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param m int整型 
     * @param u int整型vector 
     * @param v int整型vector 
     * @param x int整型vector 
     * @return bool布尔型
     */
    vector<int> node[200010];
    int sum[200010];
    int res=0;
    // 树形DP
    void dp(int x,int fa,int m,vector<int>& tmp){
        sum[x]=tmp[x-1];
        for(auto y:node[x]){

            // 遍历所有的连边的结点
            if(y==fa) continue;
            dp(y,x,m,tmp);
            sum[x]+=sum[y];
        }

        // 如果最后这个结点和它的子树构成的金币的和大于等于m，那么就将这一块进行合并
        if(sum[x]>=m){
            sum[x]=0;
            res++;
        }
    }
    bool solve(int n, int k, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        // write code here
        // 存储这颗树
        for(int i=0;i<n-1;i++){
            node[v[i]].push_back(u[i]);
            node[u[i]].push_back(v[i]);
        }

        dp(1,0,m,x);
        return res>=k;
    }
};

解法二 BFS

• 我们上面知道，我们需要从叶子节点开始向上进行扩展。那么我们如何知道叶子节点在什么位置呢？有一个好的方法是计算每个节点的入度，入度为1的就说明是叶子节点了。然后，我们将这些节点放到队列里面，不断出队往根节点的方向进行扩展。同时维护满足条件的联通块的个数。

• 代码如下

  • 队列可能会存储n个节点的情况，需要处理n个节点的情况，时间复杂度为.
  • 队列存储了n个节点的情况，而且会使用到一些数组维护权值的情况，空间复杂度为

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param m int整型 
     * @param u int整型vector 
     * @param v int整型vector 
     * @param x int整型vector 
     * @return bool布尔型
     */
    vector<int> node[200010];
    int sum[200010],in[200010];
    bool vis[200010]={false};
    bool solve(int n, int k, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        // write code here
        // 存储这颗树
        for(int i=0;i<n-1;i++){
            node[v[i]].push_back(u[i]);
            in[v[i]]++;
            node[u[i]].push_back(v[i]);
            in[u[i]]++;
        }
        queue<int> q;

        // 先把叶子结点放到放进队列里面，从树的底部一层一层扩展到根结点
        for(int i=1;i<=n;i++){
            sum[i]=x[i-1];
            if(in[i]==1){
                q.push(i);
                vis[i]=true;
            }
        }
        int res=0;
        while(!q.empty()){
            int now=q.front();
            q.pop();

            // 如果满足题目的条件，那么就执行合并的操作
            if(sum[now]>=m){
                res++;
                sum[now]=0;
            }
            for(auto y:node[now]){
                // 父节点合并子节点的权值
                sum[y]+=sum[now];


                // 如果这个结点没有被合并过
                if(!vis[y]){
                    vis[y]=true;
                    q.push(y);
                }
            }
        }
        return res>=k;
    }
};