Remove edges of a tree. Please help
mphilippov86
259

Hello! Here is a task.

Given an undirected tree of N (from 1 to 1000) nodes. Find minimal number of edges to remove to get a subtree of K (from 1 to N) nodes.

Input:
first line N and K.
on the N - 1 lines there are edges.

Output:
number of edges.

Example:
Input:
8 4
1 2
2 8
1 3
3 5
3 6
1 7
1 4

Output:
2

The program I made, gives "time limit". I need help to improve it to run faster.

#include <iostream>
#include <algorithm>
#include <vector>

using std::vector;
using std::cin;
using std::cout;
using std::endl;
using std::min;

class Graph {
public:
    Graph(size_t amount, size_t threshold);
    void addEdge(int a, int b);

    int getNumberEdges();

private:
    size_t amount;
    size_t threshold;

    const int Inf = 1e9;

    vector<size_t> used;
    vector<size_t> t_size;
    vector<vector<int>> graph;
    vector<vector<size_t>> dp;

    void fillDP(int x);
};

Graph::Graph(size_t n, size_t k)
    : amount(n)
    , threshold(k)
    , used(n)
    , t_size(n)
    , graph(n)
    , dp(n + 1, vector<size_t>(n + 1, Inf))
{}

void Graph::addEdge(int a, int b) {
    graph[a].push_back(b);
    graph[b].push_back(a);
}

int Graph::getNumberEdges() {
    fillDP(0);

    size_t ans = Inf;
    size_t i = 0;

    for (const auto &v : dp) {
        ans = min(ans, v[threshold] + bool(i));
        i++;
    }

    return ans;
}

void Graph::fillDP(int x) {
    used[x] = 1;

    for (const int u : graph[x]) {
        if (!used[u]) {
            fillDP(u);
        }
    }

    for (const int u : graph[x]) {
        t_size[x] += t_size[u];
    }

    ++t_size[x];

    dp[x][t_size[x]] = 0;
    dp[x][1] = graph[x].size();
    dp[x][0] = 1;

    for (const int num : graph[x]) {
        for (size_t j = 2; j <= t_size[x]; ++j) {
            for (size_t a = 0; a <= t_size[num] && a < j; a++) {
                const size_t diff = j - (t_size[num] - a);
                if (diff > 0) {
                    int val = (a == t_size[num] ? 1 : 0);
                    dp[x][diff] = min(dp[x][diff], dp[x][j] + dp[num][a] + val);
                }
            }
        }
    }
}

int main() {
    size_t n = 0;
    size_t k = 0;

    cin >> n >> k;

    Graph g(n, k);

    for(size_t i = 0; i < n - 1; ++i) {
        int a = 0;
        int b = 0;

        cin >> a >> b;
        g.addEdge(a - 1, b - 1);
    }

    cout << g.getNumberEdges();

    return 0;
}
Comments (0)