Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], skipTags: ["script","noscript","style","textarea","code"], processEscapes: true }});

Tree Separator

You are given a tree $T$ and an integer $K$. You can choose arbitrary distinct two vertices $u$ and $v$ on $T$. Let $P$ be the simple path between $u$ and $v$. Then, remove vertices in $P$, and edges such that one or both of its end vertices is in $P$ from $T$. Your task is to choose $u$ and $v$ to maximize the number of connected components with $K$ or more vertices of $T$ after that operation.

Input

  The input consists of a single test case formatted as follows.

$N$ $K$
$u_1$ $v_1$
:
$u_{N-1}$ $v_{N-1}$

The first line consists of two integers $N, K$ ($2 \leq N \leq 100,000, 1 \leq K \leq N$). The following $N-1$ lines represent the information of edges. The ($i+1$)-th line consists of two integers $u_i, v_i$ ($1 \leq u_i, v_i \leq N$ and $u_i \ne v_i $ for each $i$). Each $\{u_i, v_i\}$ is an edge of $T$. It's guaranteed that these edges form a tree.

Output

Print the maximum number of connected components with $K$ or more vertices in one line.

Sample Input 1

2 1
1 2

Output for Sample Input 1

0

Sample Input 2

7 3
1 2
2 3
3 4
4 5
5 6
6 7

Output for Sample Input 2

1

Sample Input 3

12 2
1 2
2 3
3 4
4 5
3 6
6 7
7 8
8 9
6 10
10 11
11 12

Output for Sample Input 3

4

Sample Input 4

3 1
1 2
2 3

Output for Sample Input 4

1

Sample Input 5

3 2
1 2
2 3

Output for Sample Input 5

0

Sample Input 6

9 3
1 2
1 3
1 4
4 5
4 6
4 7
7 8
7 9

Output for Sample Input 6

2



Sample input:
2 1
1 2


Sample output:
0

Submission status: Accepted

Solution code:
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N, K = map(int, readline().split())
    G = [[] for i in range(N)]
    for i in range(N-1):
        u, v = map(int, readline().split())
        G[u-1].append(v-1)
        G[v-1].append(u-1)
    P = [-1]*N
    vs = []
    que = deque([0])
    used = [0]*N
    used[0] = 1
    while que:
        v = que.popleft()
        vs.append(v)
        for w in G[v]:
            if used[w]:
                continue
            used[w] = 1
            que.append(w)
            P[w] = v
    sz = [0]*N; dp = [0]*N
    vs.reverse()
    ans = 0
    for v in vs:
        s = 1; d = 0
        p = P[v]
        ds = []
        for w in G[v]:
            if w == p:
                continue
            s += sz[w]
            if sz[w] >= K:
                d += 1
                ds.append(dp[w]-1)
            else:
                ds.append(dp[w])
        ds.sort(reverse=1)
        dp[v] = max(d, d + ds[0] if ds else 0)
        if ds:
            e = d + 1 if N-s >= K else d
            ans = max(ans, e + ds[0])
            if len(ds) > 1:
                ans = max(ans,  e + ds[0] + ds[1])
        sz[v] = s
    write("%d\n" % ans)
solve()