Skip to content

14184: 【原4184】树的解体

题目

题目描述

author: 失败 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4184

题目描述

一棵失败的树逃不过被分解的命运。

给定一棵含有N个节点的树,判断它能否被分为N/K个连通块,每个连通块含有的节点数都是K。

输入格式

第一行是一个正整数T,表示数据组数,对于每组数据: 第一行是两个整数N,T。接下来N-1行,每行2个整数U,V,表示节点U和V之间有边连接。 节点编号从1开始。

输出格式

对于每组数据,输出YES或者NO。

样例输入

2
4 2
1 2
2 3
3 4
4 2
1 2
1 3
1 4

样例输出

YES
NO

数据规模

对于60%的数据,\(1 \le N,K \le 1000 \)。

对于100%的数据,\(1 \le T \le 10, 1 \le N,K \le 10^5 \)。

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e6 + 100;

struct edgeNode {
    int data;
    edgeNode *next;

    edgeNode(int d = 0, edgeNode *n = 0) : data(d), next(n) {}
    ~edgeNode() {
        if (next) {
            delete next;
        }
    }
};

struct verNode {
    int data;
    int size;
    edgeNode *head;

    verNode(int d = 0, int s = 0, edgeNode *h = 0)
        : data(d), size(s), head(h) {}
    ~verNode() {
        if (head) {
            delete head;
        }
    }
};

int T, N, K;
int father[maxN] = {0}, fa;
verNode *nodes[maxN];
bool isVisited[maxN] = {0};

int DFS(int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

    for (int j = 0; j < T; j++) {
        int ans = 0;
        bool flag = 0;

        cin >> N >> K;

        for (int i = 1; i <= N; i++) {
            father[i] = 0;
            isVisited[i] = 0;
            nodes[i] = new verNode(i);
        }

        for (int i = 1; i < N; i++) {
            int temp1, temp2;
            cin >> temp1 >> temp2;
            father[temp2] = temp1;
            nodes[temp1]->head = new edgeNode(temp2, nodes[temp1]->head);
        }

        for (int i = 1; i <= N; i++) {
            if (!father[i]) {
                fa = i;
                break;
            }
        }

        DFS(fa);

        if (N % K == 0) {
            for (int i = 1; i <= N; i++) {
                if (nodes[i]->size % K == 0) {
                    ans++;
                }
            }
            if (ans == N / K) {
                flag = 1;
            }
        }

        if (flag) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }

        for (int i = 1; i <= N; i++) {
            delete nodes[i];
        }
    }

    return 0;
}

int DFS(int i) {
    if (isVisited[i]) {
        return 0;
    } else {
        isVisited[i] = 1;
        edgeNode *p = nodes[i]->head;
        while (p) {
            nodes[i]->size += DFS(p->data);
            p = p->next;
        }
        return ++(nodes[i]->size);
    }
}