# HackerEarth Tree tearing problem solution

In this HackerEarth Tree tearing problem solution, You are given a tree consisting of N vertices. What is the minimum number of vertices that should be removed so that all the remaining parts of the initial tree will contain less than K vertices?

## HackerEarth Tree tearing problem solution.

`#include <cstdio>#include <algorithm>#include <vector>#include <iostream>#include <string>#include <string.h>#include <cmath>#include <set>#include <map>#include <bitset>#include <iomanip>#define X first#define Y second#define mp make_pair#define pb push_backtypedef long long ll;using namespace std;int k, n;const int MAXN = 10100;vector<int>v[MAXN];pair<int, int>solve(int x) {    pair<int, int>res = mp(0, 0);    for (int i = 0; i < v[x].size(); i++) {        pair<int, int> cur = solve(v[x][i]);        res.X += cur.X;        res.Y += cur.Y;    }    res.Y++;    if (res.Y >= k) {        res.X++;        res.Y = 0;    }    return res;}int main() {    cin>>k>>n;    for (int i = 2; i <= n; i++) {        int x;        cin>>x;        v[x].pb(i);    }    pair<int, int>res = solve(1);    cout<<res.X<<endl;    return 0;}`

### Second solution

`#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cctype>#include<cstdlib>#include<algorithm>#include<bitset>#include<vector>#include<list>#include<deque>#include<queue>#include<map>#include<set>#include<stack>#include<cmath>#include<sstream>#include<fstream>#include<iomanip>#include<ctime>#include<complex>#include<functional>#include<climits>#include<cassert>#include<iterator>#include<unordered_set>#include<unordered_map>using namespace std;namespace test {    void end_test() {        string val;        if (cin >> val) {            exit(1);        }    }    void range_test(int t, int l, int r) {        if (t < l || r < t) {            exit(1);        }    }}#define MAX 10002int k;int n;vector<int> v[MAX];bool use[MAX];int ans=0;inline int dfs(int b){    use[b]=true;    int countt=0;    for(int i=0;i<v[b].size();i++){        if(use[v[b][i]]){            continue;        }        countt+=dfs(v[b][i]);    }    countt++;    if(countt>=k){        ans++;        countt=0;    }    return countt;}int main(){    scanf("%d",&k);    scanf("%d",&n);    test::range_test(k,1,10000);    test::range_test(n,1,10000);    for(int i=1;i<n;i++){        int a;        scanf("%d",&a);        test::range_test(a,1,i);        a--;        v[a].push_back(i);        v[i].push_back(a);    }    test::end_test();    dfs(0);    printf("%d\n",ans);    return 0;}`