P3915 树的分解

题意:给你一个含有n个结点的树(无向无环图,这个条件非常重要),判断能否按照每组k个结点,将其分成n/k组,并且要求每组仍然连通

结论:如果一个树可以被分成满足以上条件的组,那么从任意一个点出发(以任意一个结点为根)都可以将树按照上面的条件分块,并且分法唯一

将树按照无向图存储(保证任意一个结点都可以作为根,从他出发可以到达树上的任意一个结点),然后选择1号结点作为根递归求以每一个结点为根的子树大小,每当计算得到的子树大小为k时,说明找到了一组,此时令他向上一层返回的值为0,表示它的双亲结点不能和他再组合了,即他对它的双亲结点的数目贡献为0。

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int N = 100010;

int h[N], e[N << 1], ne[N << 1], idx;
int T;
int n, k, g;
int cnt[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u, int v){
    int sum = 1;

    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(j != v) sum += dfs(j, u);
        // 此处不同
        if(sum == k){
            g ++;
            return 0;
    	}
    }
    
    return sum;
}

int main(){
    cin >> T;
    
    while(T --){
        memset(h, -1, sizeof h);
        idx = 0;
        g = 0;
        
        cin >> n >> k;
        for(int i = 0; i < n - 1; i ++){
            int a, b;
            cin >> a >> b;
            
            add(a, b), add(b, a);
        }

        if(n % k){
            puts("NO");
            continue;
        }
        
        dfs(1, 0);
        
        if(g == n / k) puts("YES");
        else puts("NO");
    }
    
    return 0;
}

上面的代码在这个例子下会出错,而实际上wa了一个点...

1
3 1
1 2
1 3

输出NO,而正确答案是YES

P3915 树的分解

从1开始遍历,先到3,在3处计算得到子树大小为1,满足条件,g++并返回0,回到1所在层,sum+0=sum=1, 发现sum=1,令g++,并返回0,这样的话,最终g=2,因为结点2没有被遍历到。

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int N = 100010;

int h[N], e[N << 1], ne[N << 1], idx;
int T;
int n, k, g;
int cnt[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u, int v){ // 因为按照无向图存储,所以需要存储u是从哪走过来的,避免无限递归
    int sum = 1;

    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(j != v) sum += dfs(j, u);
    }
    
    if(sum == k){
        g ++;
        return 0;
    }
    
    return sum;
}

int main(){
    cin >> T;
    
    while(T --){
        memset(h, -1, sizeof h);
        idx = 0;
        g = 0;
        
        cin >> n >> k;
        for(int i = 0; i < n - 1; i ++){
            int a, b;
            cin >> a >> b;
            
            add(a, b), add(b, a);
        }

        if(n % k){
            puts("NO");
            continue;
        }
        
        dfs(1, 0);
        
        if(g == n / k) puts("YES");
        else puts("NO");
    }
    
    return 0;
}

复杂度\(O(NT)\)

P3915 树的分解

上一篇:ROS入门实操


下一篇:Swoft