304 North Cardinal St.
Dorchester Center, MA 02124

Minimum Subtree Cover CodeChef Solution

Minimum Subtree Cover CodeChef Solution in C++17

``````#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

using namespace std;

// #define endl '\n'
#define int long long int
#define rep(i, a, b) for (int i = a; i < b; i++)
#define revrep(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define upb(vec, val) upper_bound((vec).begin(), (vec).end(), (val)) - (vec).begin()

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

ostream &operator<<( ostream &output, const pii &p ) { output << p.first << " " << p.second;return output; }
istream &operator>>( istream &input, pii &p ) { input >> p.first >> p.second;return input; }
template<typename T>
void inline println(vector<T> args){ for(T i: args)cout<<i<<" ";cout<<endl; }
void amax(int& a, int b) { a = max(a, b); }
void amin(int& a, int b) { a = min(a, b); }
int ceilInt(int a, int b) {
if(!b) return 0;
if(a%b) return a/b + 1;
return a/b;
}

int INF = 1e18;
int MOD = 1e9+7;

vi h, depth;
vii order, inout;
int n, t;

void dfs(int v, int p) {
inout[v].first = t++;
parent[v][0] = p;
depth[v] = 0;
if(i == p) continue;
h[i] = h[v]+1;
dfs(i, v);
amax(depth[v], depth[i]+1);
}
return depth[i] < depth[j];
});
inout[v].second = t++;
}

void processParent() {
rep(j, 1, 20) {
rep(i, 0, n) {
int p = parent[i][j-1];
if(p != -1)
parent[i][j] = parent[p][j-1];
else
parent[i][j] = p;
}
}
}

bool isAncestor(int p, int v) {
return inout[p].first <= inout[v].first && inout[v].second <= inout[p].second;
}

int findLCA(int a, int b) {
if(isAncestor(a, b)) return a;
if(isAncestor(b, a)) return b;
for(int i=19; i>=0; i--) {
int p = parent[a][i];
if(p != -1 && !isAncestor(p, b))
a = p;
}
return parent[a][0];
}

void findOrder(int v, int p) {
if(i == p) continue;
findOrder(i, v);
}
if(adj[v].size() == 1 && p != -1) {
int lst = order.back().second;
int lca = findLCA(v, lst);
int pathLen = abs(h[lca]-h[v]);
order.pb({pathLen, v});
}
}

int diameterDfs() {
dfs(0, -1);
int mx = *max_element(h.begin(), h.end());
rep(i, 0, n) {
if(h[i] == mx) {
return i;
}
}
return -1;
}

void solve()
{
int k; cin>>n>>k;
t = 0;
inout.clear(), inout.resize(n);
h.clear(), h.resize(n, 0);
depth.clear(), depth.resize(n, 0);
parent.clear(), parent.resize(n, vi(20, 0));
order.clear();
rep(i, 0, n-1) {
int a, b; cin>>a>>b;
a--, b--;
}
int root = diameterDfs();
h.assign(n, 0);
depth.assign(n, 0);
order.pb({1, root});
t = 0;
dfs(root, -1);
processParent();
findOrder(root, -1);
int ans = 1; k--;
order.erase(order.begin());
sort(order.rbegin(), order.rend());
rep(i, 0, n) {
if(k <= 0) break;
k -= order[i].first;
ans++;
}
cout<<ans<<endl;
}

signed main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
// for getting input from input.txt
freopen("input.txt", "r", stdin);
// for writing output to output.txt
freopen("output.txt", "w", stdout);
#endif

int t = 1;
cin>>t;
rep(i, 0, t)
{
// cout<<"Case #"<<i+1<<": ";
solve();
}
return 0;
}``````

Minimum Subtree Cover CodeChef Solution in C++14

``````#include <bits/stdc++.h>

using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>

int getFAaaar(int node, vvi & G, int n){
vector<bool> done(n+1, false);
int Faadu=-1, far;  done[node] = true;
queue<pair<int, int>> qu; qu.push({node, 0});
while(qu.size()){
auto pi = qu.front(); qu.pop();
int nod = pi.first, dis = pi.second;
for(auto cnod: G[nod]){
if(done[cnod]) continue;
done[cnod] = true;
qu.push({cnod, dis+1});
}
}
return far;
}

void dfs(int nod, int par, vvi & G, vi & H, vi & li, int cur){
bool kiyaleafHai = true;
int mx = 0;
for(auto cnod: G[nod]) if(cnod != par) {kiyaleafHai = false; mx = max(mx, H[cnod]);}
if(kiyaleafHai){ li.push_back(cur); return; }

int c = 0;
for(auto cnod: G[nod]){
if(cnod == par) continue;
if(H[cnod] == mx && c==0){
dfs(cnod, nod, G, H, li, cur+1); c++;
}
else dfs(cnod, nod, G, H, li, 1);
}
}

void fixHeight(int nod, int par, vvi & G, vi & H){
bool kiyaleafHai = true;
for(auto cnod: G[nod]){
if(cnod == par) continue;
kiyaleafHai = false;
fixHeight(cnod, nod, G, H);
H[nod] = max(H[nod], 1 + H[cnod]);
}
if(kiyaleafHai) H[nod] = 1;
}

void breakIntoLines(int nod, int par, vvi & G, vi&li, int n){
vector<int> H(n+1, 0);
fixHeight(nod, par, G, H);
dfs(nod, par, G, H, li, 1);
}

int solutionNikal(vvi & gr, int n, int k){
if(k==1) return 1;
int u = getFAaaar(1, gr, n);
vector<int> li;
breakIntoLines(u, 0, gr, li, n);
sort(li.rbegin(), li.rend());
int size = 1, total = 0, i = 0;
while(total < k){
size++; total += li[i++];
}
return size;
}

void solve(){
int n, k;
int u, v;

cin>>n>>k;
vvi gr(n+1);
for(int i=1; i<n; i++){
cin>>u>>v;
gr[u].push_back(v); gr[v].push_back(u);
}
cout << solutionNikal(gr, n, k) << "\n";
}

int32_t main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int t;
cin>>t;
// t = 1;
int _=1;
while(t--){
// cout<<"Case #"<<_++<<": ";
solve();
}
return 0;
}``````

Minimum Subtree Cover CodeChef Solution in PYTH 3

``````"""
Url: https://www.codechef.com/problems/SUBTRCOV
"""

__author__ = "Ronald Kaiser"
__email__ = "raios dot catodicos at gmail dot com"

from sys import stdin, stdout

WHITE = 0
GRAY = 1
BLACK = 2

output_line = lambda x: stdout.write(x)

def find_farthest_leaf(N, E, root=0):
color = [WHITE] * N
farthest_leaf = root
level = 0
max_level = 0

color[root] = GRAY
stack = [root]

while stack:
cur = stack[-1]

if color[cur] == BLACK:
stack.pop()
level -= 1
continue

level += 1
if level >= max_level:
max_level = level
farthest_leaf = cur

for child in E[cur]:
if color[child] == BLACK:
continue

if color[child] == WHITE:
color[child] = GRAY
stack.append(child)

color[cur] = BLACK
return farthest_leaf

def search_strips(N, E, root):
color = [WHITE] * N
strips = [[] for _ in range(N)]
children = [[] for _ in range(N)]
leafs = [False] * N

color[root] = GRAY
stack = [root]

while stack:
cur = stack[-1]

if color[cur] == BLACK:
"""
When all children of "cur" node are processed
and it is ready to get out of the stack we can
calculate the strips it contributes to the
tree until this point, so it can be collected by its
parent later, like a DFS in a recursive approach
saving its returning value to be used by the caller.
"""
stack.pop()

new_strips = []
for child in children[cur]:
if leafs[child]:
new_strips += [1]
else:
if len(strips[child]):
strips[child][0] += 1
new_strips += strips[child]
new_strips.sort(reverse=True)
strips[cur] = new_strips
continue

for child in E[cur]:
if color[child] == BLACK:
continue

if color[child] == WHITE:
color[child] = GRAY
stack.append(child)

children[cur].append(child)
leafs[cur] = False if children[cur] else True
color[cur] = BLACK
return strips[root]

def solve(N, E, k):
if k == 1: return 1
if k == 2: return 2

farthest_leaf = find_farthest_leaf(N, E)
strips = search_strips(N, E, root=farthest_leaf)

max_k = 1
solution = 1
for strip in strips:
max_k += strip
solution += 1
if k <= max_k:
return solution

def main():
solutions = []
for _ in range(int(input())):
E = [[] for _ in range(n)]
for _ in range(n - 1):
u -= 1
v -= 1
E[u].append(v)
E[v].append(u)
solution = solve(n, E, k)
solutions.append(str(solution))
solutions = '\n'.join(solutions)
output_line(solutions)

main()``````

Minimum Subtree Cover CodeChef Solution in C

``````#include <stdio.h>
#include<stdlib.h>
int comp(const void *p, const void *q)
{
return *(int*)q - *(int*)p;
}
typedef struct
{
int deg, depth, val;
int* c;
int bfs(adj node[], int n, int p)
{
int i, q[n], front=0, rear=0, visited[n+1];
for(i=1; i<=n; i++) visited[i] = 0;
q[front++] = p;
while(front!=rear)
{
p = q[rear++];
visited[p] = 1;
for(i=0; i<node[p].deg; i++)
if(!visited[node[p].c[i]]) q[front++] = node[p].c[i];
}
return p;
}
int assigndepth(adj node[], int n, int p, int parent)
{
if(node[p].deg==1) return node[p].depth = 1;
node[p].depth = 0;
for(int i=0, v; i<node[p].deg; i++)
{
if(node[p].c[i]==parent) continue;
v = assigndepth(node, n, node[p].c[i], p);
if(node[p].depth<v) node[p].depth = v;
}
return ++node[p].depth;
}
void assignval(adj node[], int n, int p, int parent, int val)
{
int i, lc=0, lv=0; //child of longest path and length of that
node[p].val = val;
for(i=0; i<node[p].deg; i++) //find lc, lv
{
if(node[p].c[i]==parent) continue;
if(lv<node[node[p].c[i]].depth) lv=node[node[p].c[lc=i]].depth;
}
for(i=0; i<node[p].deg; i++)
{
if(node[p].c[i]==parent) continue;
if(i==lc) assignval(node, n, node[p].c[i], p, val+1);
else assignval(node, n, node[p].c[i], p, 1);
}
}
int main(void)
{
int T;
scanf("%d", &T);
while(T--)
{
int n, k, i, l=0;
scanf("%d %d", &n, &k);
int e[n-1][2], p[n+1], leafval[n];
for(i=1; i<=n; i++) node[i].deg=0;
for(i=0; i<n-1; i++)
{
scanf("%d %d", &e[i][0], &e[i][1]);
node[e[i][0]].deg++; node[e[i][1]].deg++;
}
if(k==1)
{
printf("1\n");
continue;
}
for(i=1; i<=n; i++)
{
node[i].c = (int*)malloc(node[i].deg*sizeof(int));
p[i] = 0;
}
for(i=0; i<n-1; i++)
{
node[e[i][0]].c[p[e[i][0]]++] = e[i][1];
node[e[i][1]].c[p[e[i][1]]++] = e[i][0];
}
int src = bfs(node, n, 1);
node[src].depth = assigndepth(node, n, node[src].c[0], src)+1;
//for(i=1; i<=n; i++) printf("%d %d\n",i,node[i].depth);
node[src].val=0;
assignval(node, n, node[src].c[0], src, 2);
//for(i=1; i<=n; i++) printf("%d %d\n",i,node[i].val);
for(i=1; i<=n; i++) if(node[i].deg==1) leafval[l++] = node[i].val;
qsort(leafval, l, sizeof(int), comp);
for(i=0; k>0; i++) k -= leafval[i];
printf("%d\n", i+1);
}
return 0;
}``````

Minimum Subtree Cover CodeChef Solution in JAVA

``````import java.util.*;
import java.io.*;
class SUBTRCOV{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), K = ni();
int[] from = new int[N-1], to = new int[N-1];
for(int i = 0; i< N-1; i++){
from[i] = ni()-1;
to[i] = ni()-1;
}
int[][] g = make(N, from, to);
int root = 0;
int[] dist = new int[N];Arrays.fill(dist, 2*N);
dist[0] = 0;
while(!q.isEmpty()){
int u = q.poll();
for(int v:g[u]){
if(dist[v] > dist[u]+1){
dist[v] = dist[u]+1;
}
}
}
for(int i = 0; i< N; i++)if(dist[i] > dist[root])root = i;
time = -1;
int[] eu = new int[N], st = new int[N], en = new int[N], depth = new int[N], par = new int[N];
dfs(g, par, depth, eu, st, en, root, -1);
LazySegmentTree segmentTree = new LazySegmentTree(N);
for(int i = 0; i< N; i++)segmentTree.update(st[i], st[i], depth[i]);

boolean[] inc = new boolean[N];
inc[root] = true;
int size = 1, ans = 1;
long IINF = (long)1e13;
segmentTree.update(st[root], st[root], -IINF);
while(size < K){
long[] pair = segmentTree.query(0, N-1);
int u = eu[(int)pair[0]];
ans++;
for(int cur = u; !inc[cur]; cur = par[cur]){
size++;
segmentTree.update(st[cur], st[cur], -IINF);
inc[cur] = true;
for(int v:g[cur]){
if(v == par[cur] || inc[v])continue;
}

}
}
pn(ans);
}

int time;
void dfs(int[][] g, int[] par, int[] depth, int[] eu, int[] st, int[] en, int u, int p){
par[u] = p;
eu[++time] = u;
st[u] = time;
for(int v:g[u]){
if(v == p)continue;
depth[v] = depth[u]+1;
dfs(g, par, depth, eu, st, en, v, u);
}
en[u] = time;
}
class LazySegmentTree{
int m = 1;
long IINF = (long)1e18;
long[] t, lazy;
long[] ind;
public LazySegmentTree(int n){
while(m<n)m<<=1;
t = new long[m<<1];
lazy = new long[m<<1];
ind = new long[m<<1];
for(int i = 0; i< m; i++)ind[m+i] = i;
for(int i = m-1; i> 0; i--)
ind[i] = t[i<<1] <= t[i<<1|1]?ind[i<<1]:ind[i<<1|1];
}
private void push(int i, int ll, int rr){
if(lazy[i] != 0){
t[i] += lazy[i];
if(i < m){
lazy[i<<1] += lazy[i];
lazy[i<<1|1] += lazy[i];
}
lazy[i] = 0;
}
}
public void update(int l, int r, long x){u(l, r, 0, m-1, 1, x);}
public long[] query(int l, int r){return q(l, r, 0, m-1, 1);}
public long max(int l, int r){return query(l, r)[1];}
public int argmax(int l, int r){return (int)query(l, r)[0];}

private void u(int l, int r, int ll, int rr, int i, long x){
push(i, ll, rr);
if(l == ll && r == rr){
lazy[i] += x;
push(i, ll, rr);return;
}
int mid = (ll+rr)/2;
if(r <= mid){
u(l, r, ll, mid, i<<1, x);
push(i<<1|1, mid+1, rr);
}else if(l > mid){
push(i<<1, ll, mid);
u(l, r, mid+1, rr, i<<1|1, x);
}else{
u(l, mid, ll, mid, i<<1, x);
u(mid+1, r, mid+1, rr, i<<1|1, x);
}

t[i] = Math.max(t[i<<1], t[i<<1|1]);
if(t[i] == t[i<<1])ind[i] = ind[i<<1];
if(t[i] == t[i<<1|1])ind[i] = ind[i<<1|1];
}
private long[] q(int l, int r, int ll, int rr, int i){
if(l == ll && r == rr)return new long[]{ind[i], t[i]};
int mid = (ll+rr)>>1;
if(r <= mid)return q(l, r, ll, mid, i<<1);
if(l > mid)return q(l, r, mid+1, rr, i<<1|1);
long[] p1 = q(l, mid, ll, mid, i<<1), p2 = q(mid+1, r, mid+1, rr, i<<1|1);
if(p1[1] >= p2[1])return p1;
return p2;
}
}
int[][] make(int N, int[] from, int[] to){
int[] cnt = new int[N];
for(int x:from)cnt[x]++;
for(int x:to)cnt[x]++;
int[][] g = new int[N][];
for(int i = 0; i< N; i++)g[i] = new int[cnt[i]];
for(int i = 0; i< N-1; i++){
g[from[i]][--cnt[from[i]]] = to[i];
g[to[i]][--cnt[to[i]]] = from[i];
}
return g;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new SUBTRCOV().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}``````

Minimum Subtree Cover CodeChef Solution in PYPY 3

``````import sys
from sys import path_hooks, stdin, stdout
sys.setrecursionlimit(11**(5))

from collections import deque,defaultdict,Counter
import heapq

for test in range(int(input())):
def solve():

for i in range(n-1):
u -= 1
v -= 1

if k < 4:
return min(2,k)

# method return farthest node and its distance from node u
def BFS(u):
visited = set()
distance = [-1 for i in range(n + 1)]
distance[u] = 0
queue = deque()
queue.append(u)

while queue:
front = queue.popleft()
if i not in visited:
distance[i] = distance[front]+1
queue.append(i)

maxDis = 0
for i in range(n):
if distance[i] > maxDis:
maxDis = distance[i]
node = i

return node

node = BFS(0)
depth = {}
visited = [False for i in range(n + 1)]
def bfs(u):
dd = 0
visited[u] = True
que = []
if visited[i] == False:
visited[i] = True
que.append(i)
for i in que:
dd = max(bfs(i) , dd)

depth[u] = 1 + dd
return 1 + dd

bfs(node)

exist = set()

visited = [False for i in range(n + 1)]
ele = node
while ele != -1 :
visited[ele] = True
ma = 0
n1 = -1
if visited[i] == False:
visited[i] = True
if depth[i] > ma:
ma = depth[i]
n1 = i
ele = n1
#print(exist)

exx = len(exist)

cc = Counter()
for i in depth:
if i not in exist:
cc[depth[i]] += 1

sor = sorted( list(cc.keys()) ,reverse= True)
pointer = 0

ans = 2
for i in sor:
tt = cc[i] - pointer
flag = False
for j in range(tt):
if exx >= k:
flag = True
break
exx += i
ans += 1
pointer += 1

if flag:
break

return ans

print(solve())``````

Minimum Subtree Cover CodeChef Solution in PYTH

``````import sys
from random import randint

MOD = 10**9+7
sys.setrecursionlimit(MOD)

LOG_LEVEL = 0
def log(lvl, *args):
if lvl <= LOG_LEVEL:
msg = " ".join(map(str, args))
print >> sys.stderr, "log", lvl, ":", msg

class Node:
def __init__(self, num, parent):
self.num = num
self.parent = parent
self.weight = 1

def __repr__(self):
rep = "(" + str(self.num) + ", " + \
(str(self.parent) if type(self.parent) == int else str(self.parent.num)) + ", " + \
str(self.weight) + ")"
return rep

def build_graph(n, edges):
graph = [{} for _ in xrange(n+1)]
for u, v in edges:
graph[u][v] = None
graph[v][u] = None

return graph

def solve_brute(n, k, edges):
def dfs(edges, num, parent, height, visited, leaves=None):
visited[num] = True
node = Node(num, parent)
ans = (height, [])

neighbours = graph[num]
for c in neighbours:
if not visited[c]:
ret = dfs(edges, c, node, height+1, visited, leaves)
ans = max(ans, ret)

if leaves != None and ans[1] == []:
leaves.append(node)

ans[1].append(node)
return ans

log(1, "input:", edges, k)

if k < 3:
return k

dummy = Node(0, None)
graph = build_graph(n, edges)
visited = [False for i in xrange(n+1)]
ret = dfs(edges, 1, dummy, 0, visited)

leaves = []
visited = [False for i in xrange(n+1)]
ret = dfs(edges, ret[1][0].num, dummy, 0, visited, leaves)

log(1, leaves)
diamater = ret[1]

leaves.append(leaves[0])
leaves[0] = diamater[-1]
for i in xrange(2, len(leaves)):
if leaves[i] is diamater[0]:
leaves[1], leaves[i] = leaves[i], leaves[1]
break
s = set(diamater)

log(1, leaves)
ans = 2
while len(s) < k:
log(2, len(s), k)
max_arr = []
for i in xrange(ans, len(leaves)):
ptr = leaves[i]
arr = []
while ptr not in s:
arr.append(ptr)
ptr = ptr.parent

if len(arr) > len(max_arr):
max_arr = arr
leaves[ans], leaves[i] = leaves[i], leaves[ans]

s.update(max_arr)
ans += 1
log(2, ans, leaves[ans-1])

return ans

def solve(n, k, edges):
if k < 3:
return k

graph = build_graph(n, edges)
log(9, "graph:", graph)

leaves = []
for i in xrange(1, n+1):
if len(graph[i]) == 1:
node = Node(i, graph[i].keys()[0])
leaves.append(node)
log(9, "leaves:", leaves)

m = n - k
ans = len(leaves)
while m > 0 and ans > 2:
next_leaves = []
for leaf in leaves:
p = leaf.parent
log(9, "node:", p, graph[p])

graph[p].pop(leaf.num)

if len(graph[p]) == 1:
gp = graph[p].keys()[0]
leaf.num = p
leaf.parent = gp
leaf.weight += 1
next_leaves.append(leaf)
else:
m -= leaf.weight
if m >= 0:
ans -= 1
else:
break

leaves = next_leaves

return max(2, ans)

def main():
t = int(raw_input())
for _ in xrange(t):
n, k = map(int, raw_input().split())
edges = []
for _ in xrange(n-1):
e = map(int, raw_input().split())
edges.append(e)

ans = solve(n, k, edges)
print ans

def alternate():
n = 100
same = True

edges = [[1, 2], [2, 3], [3, 4], [3, 5]]
k = 5

m = 0
while same:
log(9, "solve")
ans = solve(len(edges)+1, k ,edges)
log(9, "fast")
ans_brute = solve_brute(len(edges)+1, k, edges)

if ans_brute != ans:
same = False
print n, k, edges
print ans
print ans_brute

edges = []
for i in xrange(2, n + 1):
edges.append([randint(1, i-1), i])
k = randint(1, n)

m += 1
if m%1000 == 0:
print m

exit(0)

if __name__ == '__main__':
#alternate()
main()``````

Minimum Subtree Cover CodeChef Solution in C#

``````using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace CSharpSolution.JUNE21C.SUBTRCOV
{
class Tree
{
//public List<int> minWithout;
//public List<int> minWith;
//public bool done = false;
//public int depth = 0;
public int impact = -1;
//public int id;
public Tree()
{
//minWithout = new List<int>();
//minWith = new List<int>();
//minWithout.Add(0); // 0 nodes -> 0
//minWith.Add(0); // 0 nodes -> 0
//minWith.Add(1); // 1 node -> 1
//this.id = id;
}

{
}

/* public bool AllChildrenDone()
{
int notDone = 0;
foreach (Tree t in children)
{
if (!t.done)
{
notDone++;
}
if (notDone > 1)
{
return false;
} // else  // We are a leaf node, our only child is the parent.
}
return true;
}*/

public void ComputeImpact()
{
impact = 1;
Debug.Assert(children.Count == 1);
Tree target = children.First();
Tree previous = this;
while (target.children.Count == 2)
{
impact++;
if (target.children.First() == previous)
{
previous = target;
target = target.children.Last();
}
else
{
previous = target;
target = target.children.First();
}
}
}

public void UpdateParent()
{
// We are removing this leaf, first we need to remove all nodes as long as they are leafes
Debug.Assert(children.Count == 1);
Tree target = children.First();
Tree previous = this;
while (target.children.Count == 2)
{
if (target.children.First() == previous)
{
previous = target;
target = target.children.Last();
}
else
{
previous = target;
target = target.children.First();
}
}
// We now have our target, it should no longer point to the previous one
target.children.Remove(previous);
// If this now becomes part of a chain, we need to update the ends of the chain:
Debug.Assert(target.children.Count >= 2);
if (target.children.Count == 2)
{
// Go up and down to update both ends
Tree targetUp = target.children.First();
Tree previousUp = target;
int stepsUp = 0;
int stepsDown = 0;
// UP/DOWN
while (targetUp.children.Count == 2)
{
stepsUp++;
if (targetUp.children.First() == previousUp)
{
previousUp = targetUp;
targetUp = targetUp.children.Last();
}
else
{
previousUp = targetUp;
targetUp = targetUp.children.First();
}
}
Tree targetDown = target.children.Last();
Tree previousDown = target;
while (targetDown.children.Count == 2)
{
stepsDown++;
if (targetDown.children.First() == previousDown)
{
previousDown = targetDown;
targetDown = targetDown.children.Last();
}
else
{
previousDown = targetDown;
targetDown = targetDown.children.First();
}
}
if (targetUp.children.Count == 1)
{
// targetUp is a leaf, add new impact
targetUp.impact += stepsDown + 1;
if (targetDown.children.Count == 1)
{
targetUp.impact++;
}
}
if (targetDown.children.Count == 1)
{
// targetDown is a leaf, add new impact
targetDown.impact += stepsUp + 1;
if (targetUp.children.Count == 1)
{
targetDown.impact++;
}
}

}
}

/*
{
// A bit of safety margin because we access [2] explicitly
maxK = Math.Max(maxK, 3);
done = true;
var childrenDone = new List<Tree>();
foreach (var c in children)
{
if (c.done)
{
}
}
if (childrenDone.Count == 0)
{
return;
}
// We have to fill data up to the maximum size

// First our depth
int maxDepth = 0;
int maxNodeCount = 0;
foreach (Tree c in childrenDone)
{
maxDepth = Math.Max(maxDepth, c.depth);
maxNodeCount += Math.Max(c.minWith.Count, c.minWithout.Count);
}
// Increase by one to account for us
maxDepth++;
maxNodeCount++;
maxNodeCount = Math.Min(maxK + 1, maxNodeCount);
depth = maxDepth;

// Now the tricky part
while (minWithout.Count <= maxNodeCount)
{
}
while (minWith.Count <= maxNodeCount)
{
}

// We can join trees together, this will include us if we don't just copy the value from one tree +1
// We add one tree after another
foreach (Tree c in childrenDone)
{
var newWith = new List<int>(minWith);
var newWithout = new List<int>(minWithout);
// For j=1 we would remove the whole tree, no good
for (int j = 1; j < c.minWith.Count; j++)
{
if (c.minWith[j] == 0)
{
continue;
}
if (j == 1)
{
// For j=1 we would drop the whole tree, unless we keep it as a single node
// that we add to our exisiting tree.
// If we add it additional to our root, we can just add 1 for our root
for (int i = 1; i < newWith.Count; i++)
{
newWith[i] = Math.Max(newWith[i], minWith[i - 1] + 1);
}
// If we add it and we don't have our root then that would include
// our root automatically (us+root) = +2 total and +1 node count
// Problem is that we might already include the root node.
// So the proper way it to base this of the case where we include the root node
// and just move the root node to our new position
for (int i = 2; i < newWithout.Count; i++)
{
newWithout[i] = Math.Max(newWithout[i], minWith[i] + 1);
}

continue;
}

// J=2 and this includes the root node, if we join it with either us
// or another tree, we can remove the root node -> get one for free

// First option just put as as root (the number of nodes stays but we add one node (us))
newWith[j] = Math.Max(newWith[j], 1 + c.minWith[j]);

// Second Option, join it with another subtree
for (int i = 1; i + j - 1 < minWithout.Count; i++)
{
if (minWithout[i] == 0)
{
// No method of achieving this
continue;
}
// -1 because we no longer need the root node from C
int target = i + j - 1;
int total = minWithout[i] + c.minWith[j];
if (total > newWithout[target])
{
newWithout[target] = total;
}
}

// Third option, we can just move the root node up
for (int i = 1; i + j - 1 < minWith.Count; i++)
{
if (minWith[i] == 0)
{
// No method of achieving this
continue;
}
// -1 because we no longer need the root node from C
int target = i + j - 1;
int total = minWith[i] + c.minWith[j];
if (total > newWith[target])
{
newWith[target] = total;
}

if (i > 1)
{
// If we have the root node and some other side tree
// we could also give up the root of both us and the side tree
target = i + j - 2;
newWithout[target] = Math.Max(newWithout[target], minWith[i] + c.minWith[j]);
}
}
}
minWith = newWith;
minWithout = newWithout;

// With us as root
if (c.depth + 2 > minWith[2])
{
minWith[2] = c.depth + 2;
}

// Without Us 1
for (int j = 1; j < c.minWithout.Count; j++)
{
minWithout[j] = Math.Max(minWithout[j], c.minWithout[j]);
}
// Without Us 2
for (int j = 1; j < c.minWith.Count; j++)
{
minWithout[j] = Math.Max(minWithout[j], c.minWith[j]);
}
}

int max = 0;
foreach (int i in minWith)
{
max = Math.Max(i, max);
}
int firstLower = minWith.Count;
for (int i = minWith.Count - 1; i > 0; i--)
{
if (minWith[i] < max)
{
firstLower = i;
}
else
{
break;
}
}
if (firstLower < minWith.Count)
{
minWith.RemoveRange(firstLower, minWith.Count - firstLower);
}

max = 0;
foreach (int i in minWithout)
{
max = Math.Max(i, max);
}
firstLower = minWithout.Count;
for (int i = minWithout.Count - 1; i > 0; i--)
{
if (minWithout[i] < max)
{
firstLower = i;
}
else
{
break;
}
}
if (firstLower < minWithout.Count)
{
minWithout.RemoveRange(firstLower, minWithout.Count - firstLower);
}
}*/

}

class SUBTRCOV
{
/*
static int SmallestSubset(List<Tree> nodes, int k)
{
if (k <= 1)
{
return 1;
}
int maxK = 0;
foreach (Tree t in nodes)
{
if (t.children.Count == 1)
{
// Leaf node!
maxK++;
}
}
Queue<Tree> toDo = new Queue<Tree>(nodes);

while (toDo.Count > 0)
{
var node = toDo.Dequeue();
// Check if all children are known, otherwise put it back in the queue
// In order to call this function multiple times, skip things that are done
if (node.done)
{
continue;
}

if (node.AllChildrenDone())
{
}
else
{
toDo.Enqueue(node);
}
}
// Do this only once we are done

int minV = int.MaxValue;
foreach (Tree node in nodes)
{
for (int i = 1; i < node.minWithout.Count && i < minV; i++)
{
if (node.minWithout[i] >= k)
{
minV = i;
break;
}
}
for (int i = 1; i < node.minWith.Count && i < minV; i++)
{
if (node.minWith[i] >= k)
{
minV = i;
break;
}
}

}
if (minV > nodes.Count)
{
throw new Exception("Not possible");
}
return minV;

}*/

static Tree getWorstTree(List<Tree> leafes)
{
Tree lowest = leafes[0];
for (int i = 0; i < leafes.Count; i++)
{
if (leafes[i].impact < lowest.impact)
lowest = leafes[i];
}
return lowest;
}

static int SmallestSubsetV2(List<Tree> nodes, int k)
{
if (k <= 1)
{
return 1;
}
List<Tree> leafes = new List<Tree>();
foreach (Tree t in nodes)
{
if (t.children.Count == 1)
{
// Leaf node!
t.ComputeImpact();
}
}
int currentCover = nodes.Count;
int currentSSize = leafes.Count;
leafes.Sort((t1, t2) => t2.impact.CompareTo(t1.impact));
int[] bestTreePossible = new int[leafes.Count];
for (int i = 0; i < leafes.Count; i++)
{
bestTreePossible[i] = leafes[i].impact;
}
int counter = leafes.Count - 1;
int foundLast = bestTreePossible[counter];
int LC = leafes.Count;
int LCM = LC - 1;
while (currentCover > k && LC > 0)
{
// Remove the leaf with the lowest number:
int lowestIdx = LCM;
int lowestValue = leafes[lowestIdx].impact;
if (foundLast != lowestValue)
{
for (int i = LCM; i >= 0; i--)
{
if (leafes[i].impact < lowestValue)
{
lowestIdx = i;
lowestValue = leafes[i].impact;
if (foundLast == lowestValue)
{
break;
}
}
}
}
foundLast = Math.Min(lowestValue, bestTreePossible[counter]);
if (currentCover - lowestValue < k)
{
// Too much impact
break;
}
currentCover -= lowestValue;
currentSSize--;
leafes[lowestIdx].UpdateParent();
// Make sure we don't consider this one
leafes.RemoveAt(lowestIdx);
LC--;
LCM--;
counter--;
if (LC > 1000 && LC - lowestIdx > 300)
{
leafes.Sort((t1, t2) => t2.impact.CompareTo(t1.impact));

for (int i = 0; i < LC; i++)
{
bestTreePossible[i] = leafes[i].impact;
}
}
}
return currentSSize;
}

static void Main(string[] args)
{
// System.IO.StreamWriter file = new System.IO.StreamWriter("output.txt", append: true);
for (int i = 0; i < t; i++)
{
int split = line.IndexOf(' ');
int n = int.Parse(line.Substring(0, split));
int k = int.Parse(line.Substring(split));
List<Tree> nodes = new List<Tree>(n);
for (int j = 0; j < n; j++)
{
}

for (int j = 0; j < n - 1; j++)
{
split = line.IndexOf(' ');
int from = int.Parse(line.Substring(0, split)) - 1;
int to = int.Parse(line.Substring(split)) - 1;
}

/*Console.WriteLine("Debug Output");
// Remove
for (int kS = 1; kS <= nodes.Count; kS++)
{
Console.WriteLine(\$"k:{kS:00} S:{SmallestSubset(nodes, kS)}");
}*/

//file.WriteLine(SmallestSubset(nodes, k));
Console.WriteLine(SmallestSubsetV2(nodes, k));

}
//file.Close();
//Console.WriteLine("Done");
}
}
}``````

Minimum Subtree Cover CodeChef Solution in GO

``````package main

import (
"bufio"
"bytes"
"fmt"
"os"
)

func main() {
var buf bytes.Buffer

for tc > 0 {
tc--
E := make([][]int, n-1)

for i := 0; i < n-1; i++ {
}
res := solve(n, E, m)
buf.WriteString(fmt.Sprintf("%d\n", res))
}
fmt.Print(buf.String())
}

func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}

return
}

a, b = res[0], res[1]
return
}

a, b, c = res[0], res[1], res[2]
return
}

res := make([]int, n)
x := 0
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
}
return res
}

func readUint64(bytes []byte, from int, val *uint64) int {
i := from

var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp

return i
}

func solve(n int, E [][]int, k int) int {
g := NewGraph(n, len(E)*2)

for _, e := range E {
}

dist := make([]int, n)
var dfs func(p, u int)

dfs = func(p, u int) {
for i := g.nodes[u]; i > 0; i = g.next[i] {
v := g.to[i]
if p != v {
dist[v] = dist[u] + 1
dfs(u, v)
}
}
}

dfs(0, 0)

var root int

for i := 0; i < n; i++ {
if dist[i] > dist[root] {
root = i
}
}

var time = -1
eu := make([]int, n)
open := make([]int, n)
end := make([]int, n)
P := make([]int, n)

var dfs2 func(p, u int)
dfs2 = func(p, u int) {
time++
eu[time] = u
open[u] = time
for i := g.nodes[u]; i > 0; i = g.next[i] {
v := g.to[i]
if v != p {
P[v] = u
dist[v] = dist[u] + 1
dfs2(u, v)
}
}
end[u] = time
}
dist[root] = 0
dfs2(root, root)

lt := NewLazyTree(n)

for i := 0; i < n; i++ {
lt.Update(open[i], open[i], dist[i])
}

set := make([]bool, n)
set[root] = true
lt.Update(open[root], open[root], -(n + 1))
ans := 1
k--
for k > 0 {
pair := lt.Query(0, n-1)
u := eu[pair[0]]
ans++
for cur := u; !set[cur]; cur = P[cur] {
k--
lt.Update(open[cur], open[cur], -(n + 1))
set[cur] = true
for i := g.nodes[cur]; i > 0; i = g.next[i] {
v := g.to[i]
if P[cur] == v || set[v] {
continue
}
}
}
}

return ans
}

type Graph struct {
nodes []int
next  []int
to    []int
cur   int
}

func NewGraph(n int, e int) *Graph {
g := new(Graph)
g.nodes = make([]int, n)
g.next = make([]int, e+3)
g.to = make([]int, e+3)
g.cur = 0
return g
}

func (g *Graph) AddEdge(u, v int) {
g.cur++
g.next[g.cur] = g.nodes[u]
g.nodes[u] = g.cur
g.to[g.cur] = v
}

type LazyTree struct {
tree []int
lazy []int
ind  []int
n    int
m    int
}

func NewLazyTree(n int) *LazyTree {
m := 1
for m < n {
m <<= 1
}
lt := new(LazyTree)

lt.n = n
lt.m = m
lt.tree = make([]int, m<<1)
lt.lazy = make([]int, m<<1)
lt.ind = make([]int, m<<1)
for i := m; i < len(lt.ind); i++ {
lt.ind[i] = i - m
}

for i := m - 1; i > 0; i-- {
if lt.tree[i*2] <= lt.tree[i*2+1] {
lt.ind[i] = lt.ind[2*i]
} else {
lt.ind[i] = lt.ind[2*i+1]
}
}

return lt
}

func (lt *LazyTree) push(i int) {
if lt.lazy[i] != 0 {
lt.tree[i] += lt.lazy[i]
if i < lt.m {
lt.lazy[i*2] += lt.lazy[i]
lt.lazy[i*2+1] += lt.lazy[i]
}
lt.lazy[i] = 0
}
}

func (lt *LazyTree) Query(l, r int) []int {
var loop func(l, r int, ll, rr int, i int) []int
loop = func(l, r int, ll, rr int, i int) []int {
if l == ll && r == rr {
return []int{lt.ind[i], lt.tree[i]}
}
mid := (ll + rr) / 2
if r <= mid {
return loop(l, r, ll, mid, i*2)
}
if mid < l {
return loop(l, r, mid+1, rr, i*2+1)
}

a := loop(l, mid, ll, mid, i*2)
b := loop(mid+1, r, mid+1, rr, i*2+1)

if a[1] >= b[1] {
return a
}
return b
}

return loop(l, r, 0, lt.m-1, 1)
}

func (lt *LazyTree) Update(l, r int, x int) {

var loop func(l, r, ll, rr int, i int)

loop = func(l, r, ll, rr int, i int) {
lt.push(i)
if l == ll && r == rr {
lt.lazy[i] += x
lt.push(i)
return
}
mid := (ll + rr) / 2
if r <= mid {
loop(l, r, ll, mid, i*2)
lt.push(2*i + 1)
} else if mid < l {
lt.push(2 * i)
loop(l, r, mid+1, rr, i*2+1)
} else {
loop(l, mid, ll, mid, i*2)
loop(mid+1, r, mid+1, rr, i*2+1)
}

lt.tree[i] = max(lt.tree[2*i], lt.tree[2*i+1])
if lt.tree[i] == lt.tree[2*i] {
lt.ind[i] = lt.ind[2*i]
} else {
lt.ind[i] = lt.ind[2*i+1]
}
}
loop(l, r, 0, lt.m-1, 1)
}

func max(a, b int) int {
if a >= b {
return a
}
return b
}``````
Minimum Subtree Cover CodeChef Solution Review:

In our experience, we suggest you solve this Minimum Subtree Cover CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Minimum Subtree Cover CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Minimum Subtree Cover CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!