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


HackerEarth Tree tearing problem solution


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_back

typedef 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 10002

int 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;
}