Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Minimum Subtree Cover CodeChef Solution
Problem -Minimum Subtree Cover CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
<<Previous CodeChef Problem Next Codechef Problem>>
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;
vector<vi> adj, parent;
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;
for(int i: adj[v]) {
if(i == p) continue;
h[i] = h[v]+1;
dfs(i, v);
amax(depth[v], depth[i]+1);
}
sort(adj[v].rbegin(), adj[v].rend(), [&](int i, int j) {
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) {
for(int i: adj[v]) {
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);
adj.clear(), adj.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--;
adj[a].pb(b);
adj[b].pb(a);
}
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;
if(Faadu < dis) Faadu = dis, far = nod;
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
read_numbers = lambda: list(map(int, stdin.readline().strip().split()))
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())):
n, k = read_numbers()
E = [[] for _ in range(n)]
for _ in range(n - 1):
u, v = read_numbers()
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;
} adj;
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];
adj node[n+1];
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;
Queue<Integer> q = new LinkedList<>();
q.add(0);
while(!q.isEmpty()){
int u = q.poll();
for(int v:g[u]){
if(dist[v] > dist[u]+1){
dist[v] = dist[u]+1;
q.add(v);
}
}
}
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]];
int add = (int)pair[1];
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;
segmentTree.update(st[v], en[v], -add);
}
add--;
}
}
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;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
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());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}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():
n,k = map(int, stdin.readline().split())
adj = defaultdict(list)
for i in range(n-1):
u,v = map(int, stdin.readline().split())
u -= 1
v -= 1
adj[u].append(v)
adj[v].append(u)
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)
visited.add(u)
while queue:
front = queue.popleft()
for i in adj[front]:
if i not in visited:
visited.add(i)
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 = []
for i in adj[u]:
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 :
exist.add(ele)
visited[ele] = True
ma = 0
n1 = -1
for i in adj[ele]:
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 LinkedList<Tree> children;
//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
children = new LinkedList<Tree>();
//this.id = id;
}
public void AddChild(Tree t)
{
children.AddLast(t);
}
/* 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++;
}
}
}
}
/*
public void UpdateSelf(int maxK)
{
// 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)
{
childrenDone.Add(c);
}
}
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)
{
minWithout.Add(0);
}
while (minWith.Count <= maxNodeCount)
{
minWith.Add(0);
}
// 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())
{
node.UpdateSelf(maxK);
}
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();
leafes.Add(t);
}
}
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);
int t = int.Parse(Console.ReadLine());
for (int i = 0; i < t; i++)
{
string line = Console.ReadLine();
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++)
{
nodes.Add(new Tree());
}
for (int j = 0; j < n - 1; j++)
{
line = Console.ReadLine();
split = line.IndexOf(' ');
int from = int.Parse(line.Substring(0, split)) - 1;
int to = int.Parse(line.Substring(split)) - 1;
nodes[from].AddChild(nodes[to]);
nodes[to].AddChild(nodes[from]);
}
/*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() {
reader := bufio.NewReader(os.Stdin)
var buf bytes.Buffer
tc := readNum(reader)
for tc > 0 {
tc--
n, m := readTwoNums(reader)
E := make([][]int, n-1)
for i := 0; i < n-1; i++ {
E[i] = readNNums(reader, 2)
}
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
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
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 {
g.AddEdge(e[0]-1, e[1]-1)
g.AddEdge(e[1]-1, e[0]-1)
}
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]]
add := pair[1]
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
}
lt.Update(open[v], end[v], -add)
}
add--
}
}
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.
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!
