Quick Exit
Source: codechef
Difficulty: 2475

Quick Exit
This problem has the same setup and constraints as QUICKEXIT. The only difference is that in this version, you only need to compute the minimum time.
You're given a tree with$N$vertices rooted at vertex$1$.
One person stands at each vertex, the strength of the person at vertex$i$is denoted$P_i$. All strengths are between$1$and$N$, and distinct.
Repeat the following process while at least one person remains:
The person standing at the root leaves the tree.
Then, for every vertex$u$such that$u$is empty but some child of$u$is not empty, the person with maximum strength standing at a child of$u$will move to$u$.
This repeats till no such$u$exists, then go back to step$1$.
The whole two-step process of one person leaving the tree and others moving to fill in the gaps takes one second, so after exactly$N$seconds, the tree will have no more people in it.
You're standing at vertex$N$, and have a strength of$K$.
The strengths of the other people are unknown.
There are$(N-1)!$ways to assign the strengths of the other people.
Across all of them, find the minimum possible time you can leave.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains two space-separated integers$N$and$K$— the number of vertices in the tree, and your strength.
The next$N-1$lines describe the edges. The$i$-th of these$N-1$lines contains two space-separated integers$u_i$and$v_i$, denoting an edge between$u_i$and$v_i$.
Output Format
For each test case, output on a new line one integer: the minimum possible time at which you can exit.
Constraints$1 \leq T \leq 1000$$1 \leq N \leq 3000$$1 \leq K \leq N$The input edges describe a tree on$N$vertices.
The sum of$N$over all test cases won't exceed$3000$.
Sample 1:
Explanation:
Test case$1$:
Consider the assignment of strengths$P = [2, 1, 3]$. Note that$P_N = 3 = K$as required. Now,
Second$1$:
The following sequence of movements will occur:
The person standing at the root, with strength$2$, will leave.
Among the children of the root, the strengths are$P_2 = 1$and$P_3 = 3$. So, the person with strength$3$(i.e. you) will move up.
The strengths are now$[3, 1, 0]$.
Second$2$:
You will leave the tree, since you're at the root.
This is optimal.
Test case$2$:
Same tree as before, but$K = 1$now. Whether$P = [1, 2, 3]$or$P = [2, 1, 3]$, you will leave the tree last, since the person at vertex$2$will always move up before you.
So, the answer is$3$.
Test case$3$:
One optimal assignment is$P = [5, 4, 1, 2, 3]$.
In the first second,$P_1 = 5$will leave, and$P_5 = 3$and$P_2 = 4$will move up. After this, we have$P = [3, 0, 1, 2, 4]$, with nobody standing at vertex$2$.
Next, the person with strength$3$(which is you) will leave the tree (and the remainder of the process doesn't matter).
This way, it's possible to leave the tree in two seconds. This is optimal.

Sample Input:
4
3 3
1 2
1 3
3 1
1 2
1 3
5 3
1 4
2 5
3 4
5 1
6 2
1 2
1 3
3 4
1 6
6 5

Sample Output:
2
3
2
3

C++ solution:
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n, x; cin >> n >> x;

        vector adj(n+1, vector<int>());
        for (int i = 1; i < n; ++i) {
            int u, v; cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        vector<int> par(n+1), children(n+1), subsz(n+1);
        auto dfs = [&] (const auto &self, int u, int p) -> void {
            par[u] = p;
            subsz[u] = 1;
            for (int v : adj[u]) if (v != p) {
                self(self, v, u);
                subsz[u] += subsz[v];
                ++children[u];
            }
        };
        dfs(dfs, 1, 0);

        if (x == 1) {
            cout << n - subsz[n] + 1 << '\n';
            continue;
        }

        auto solve = [&] () {
            vector<int> onpath(n+1);
            int important = 0;
            {
                int cur = n;
                while (cur > 1) {
                    onpath[cur] = 1;
                    important += children[par[cur]] - 1;
                    cur = par[cur];
                }
                onpath[cur] = 1;
            }

            if (important >= x - 1) {
                // Distribute small values to the important nodes with largest subtree sizes
                vector<int> subsizes;
                for (int i = 2; i < n; ++i) {
                    if (!onpath[i] and onpath[par[i]] and par[i] != n) {
                        subsizes.push_back(subsz[i]);
                    }
                }
                sort(rbegin(subsizes), rend(subsizes));

                int delay = accumulate(begin(subsizes) + x-1, end(subsizes), 0);
                cout << accumulate(begin(onpath), end(onpath), 0) + delay << '\n';
                return;
            }
            
            // Other case: there's enough small things
            // Answer is just number of vertices on the path
            cout << accumulate(begin(onpath), end(onpath), 0) << '\n';
        };

        solve();
    }
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1024*1024), 1024*1024)

	scanner.Scan()
	T, _ := strconv.Atoi(scanner.Text())

	for t := 0; t < T; t++ {
		scanner.Scan()
		N, _ := strconv.Atoi(scanner.Text())
		scanner.Scan()
		K, _ := strconv.Atoi(scanner.Text())

		adj := make([][]int, N+1)
		for i := 0; i < N-1; i++ {
			scanner.Scan()
			u, _ := strconv.Atoi(scanner.Text())
			scanner.Scan()
			v, _ := strconv.Atoi(scanner.Text())
			adj[u] = append(adj[u], v)
			adj[v] = append(adj[v], u)
		}

		parent := make([]int, N+1)
		stack := []int{1}
		parent[1] = 0

		for len(stack) > 0 {
			x := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			for _, v := range adj[x] {
				if v != parent[x] {
					parent[v] = x
					stack = append(stack, v)
				}
			}
		}

		path := []int{}
		x := N
		for x != 1 {
			path = append(path, x)
			x = parent[x]
		}
		path = append(path, 1)

		c := []int{}
		for i := 0; i < len(path)-1; i++ {
			y := path[i+1]
			for _, v := range adj[y] {
				if v != path[i] && v != parent[y] {
					cnt := 0
					stack := []int{v}
					for len(stack) > 0 {
						z := stack[len(stack)-1]
						stack = stack[:len(stack)-1]
						cnt++
						for _, u := range adj[z] {
							if u != parent[z] {
								stack = append(stack, u)
							}
						}
					}
					c = append(c, cnt)
				}
			}
		}

		sort.Sort(sort.Reverse(sort.IntSlice(c)))
		ans := len(path) - 1
		m := len(c)
		for i := K - 1; i < m; i++ {
			ans += c[i]
		}
		fmt.Println(ans + 1)
	}
}

Java solution:
import java.io.*;
import java.util.*;

public class Main implements Runnable {
    private static void solve(MyScanner in, PrintWriter out) {
        int n = in.nextInt();
        int k = in.nextInt();
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt() - 1;
            int v = in.nextInt() - 1;
            adj[u].add(v);
            adj[v].add(u);
        }
        if (n == 1) {
            out.println(1);
            return;
        }
        int[] p = new int[n];
        int[] subtree = new int[n];
        p[0] = -1;
        dfs(adj, 0, -1, p, subtree);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int res = 1;
        for (int w = p[n - 1], prev = n - 1; w != -1; prev = w, w = p[w]) {
            res++;
            for (int u : adj[w]) {
                if (u != p[w] && u != prev) pq.add(subtree[u]);
            }
        }
        while (pq.size() >= k) res += pq.poll();
        out.println(res);
    }

    private static void dfs(List<Integer>[] adj, int v, int parent, int[] p, int[] subtree) {
        subtree[v]++;
        for (int w : adj[v]) {
            if (w == parent) continue;
            p[w] = v;
            dfs(adj, w, v, p, subtree);
            subtree[v] += subtree[w];
        }
    }

    public static void main(String[] args) {
        new Thread(null, new Main(), "Main", 1 << 28).start();
    }

    public void run() {
        MyScanner in = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int t = in.nextInt();
        for (int i = 1; i <= t; i++) {
            solve(in, out);
        }
        out.close();
    }

    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

    }
    //--------------------------------------------------------
}

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github :  https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

// Template Starts here Fast IO!

const V8Flags = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];

if (V8Flags.length > 0) {
        process.execArgv.push('--v8-options=' + V8Flags.join(' '));
}

const inputBuffer = Buffer.allocUnsafe(1e7);
let inputIndex = 0,
        inputLength = 0;
const outputBuffer = Buffer.allocUnsafe(1e7);
let outputIndex = 0;

const fs = require('fs');
inputLength = fs.readSync(process.stdin.fd, inputBuffer, 0, inputBuffer.length, null);

function readInt() {
        let n = 0,
                s = 1;
        while (inputBuffer[inputIndex] < 48 || inputBuffer[inputIndex] > 57) {
                if (inputBuffer[inputIndex] === 45) s = -1;
                inputIndex++;
        }
        while (inputIndex < inputLength && inputBuffer[inputIndex] >= 48 && inputBuffer[inputIndex] <= 57) {
                n = n * 10 + (inputBuffer[inputIndex++] - 48);
        }
        return n * s;
}

function writeInt(v, isLast = false) {
        if (outputIndex > 0 && !isLast) outputBuffer[outputIndex++] = 32;
        if (v < 0) {
                outputBuffer[outputIndex++] = 45;
                v = -v;
        }
        let d = [];
        do {
                d.push(v % 10);
                v = Math.floor(v / 10);
        } while (v > 0);
        for (let i = d.length - 1; i >= 0; i--) {
                outputBuffer[outputIndex++] = 48 + d[i];
        }
        if (isLast) outputBuffer[outputIndex++] = 10;
}

// Template Ends here!

let q = readInt();
while (q--) {
        let n = readInt(),
                k = readInt() - 1;
        let g = Array.from({
                length: n
        }, () => []);
        for (let i = 0; i < n - 1; i++) {
                let u = readInt() - 1,
                        v = readInt() - 1;
                g[u].push(v);
                g[v].push(u);
        }
        let t = Array.from({
                length: n
        }, () => []);
        let pi = Array(n).fill(Infinity),
                d = Array(n).fill(-1);
        d[0] = 0;
        let q = [0];
        for (let i = 0; i < q.length; i++) {
                let v = q[i];
                for (let a of g[v]) {
                        if (d[a] === -1) {
                                d[a] = d[v] + 1;
                                t[v].push(a);
                                pi[a] = v;
                                q.push(a);
                        }
                }
        }
        let sz = Array(n).fill(1);
        for (let i = q.length - 1; i >= 0; i--) {
                let v = q[i];
                for (let a of t[v]) sz[v] += sz[a];
        }
        let cur = n - 1,
                p = [cur];
        while (pi[p[p.length - 1]] !== Infinity) p.push(pi[p[p.length - 1]]);
        p.reverse();
        let ans = n - sz[cur] + 1,
                s = [],
                st = new Set(p);
        p.pop();
        for (let v of p) {
                for (let a of t[v]) {
                        if (!st.has(a)) s.push(sz[a]);
                }
        }
        s.sort((a, b) => b - a);
        ans -= s.slice(0, k).reduce((sum, val) => sum + val, 0);
        writeInt(ans, true);
}
fs.writeSync(process.stdout.fd, outputBuffer.slice(0, outputIndex));

Python solution:
#author: sushmanth
from sys import stdin , stdout , setrecursionlimit
input = stdin.readline
setrecursionlimit(10000)

inp = lambda : list(map(int , input().split()))

def answer():
    global down

    take = []
    subtree = [0 for i in range(n + 1)]
    def dfs(p , prev , lvl = 0):
        global down

        subtree[p] , found = 1 , -1
        for i in child[p]:
            if(i == prev):continue
            if(dfs(i , p , lvl + 1)):
                found = i
            subtree[p] += subtree[i]

        if(found != -1):
            for i in child[p]:
                if(i == prev):continue
                if(found == i):continue
                take.append(subtree[i])

        if(p == n):down = lvl
        if(found != -1 or p == n):
            return True

        return False
        

    dfs(1 , -1)
    take.sort(reverse = True)

    ans = down + 1
    for x in range(k - 1 , len(take)):
        ans += take[x]

    return ans

for T in range(int(input())):

    n , k = inp()
    child = [[] for i in range(n + 1)]
    for i in range(n - 1):
        u , v = inp()
        child[u].append(v)
        child[v].append(u)

    print(answer())

Ruby solution:
require 'set'

def solve
  input = $stdin.read.split
  ptr = 0
  test_cases = input[ptr].to_i
  ptr += 1
  test_cases.times do
    n, k = input[ptr, 2].map(&:to_i)
    ptr += 2
    child = Array.new(n + 1) { [] }
    (n - 1).times do
      u, v = input[ptr, 2].map(&:to_i)
      ptr += 2
      child[u] << v
      child[v] << u
    end

    down = 0
    take = []
    subtree = Array.new(n + 1, 0)

    dfs = lambda do |p, prev, lvl|
      subtree[p] = 1
      found = -1
      child[p].each do |i|
        next if i == prev
        if dfs.call(i, p, lvl + 1)
          found = i
        end
        subtree[p] += subtree[i]
      end

      if found != -1
        child[p].each do |i|
          next if i == prev || i == found
          take << subtree[i]
        end
      end

      if p == n
        down = lvl
      end

      found != -1 || p == n
    end

    dfs.call(1, -1, 0)

    take.sort!.reverse!

    ans = down + 1
    (k - 1).upto(take.size - 1) do |x|
      ans += take[x] if x >= 0
    end

    puts ans
  end
end

solve