(Analysis by Benjamin Qi)

Root the tree at $1$. We will do DP on subtrees.

It suffices to binary search on $K.$ We should write a function $DFS(x)$ which partitions the subtree corresponding to vertex $x$ into paths of length at least $K$ and possibly an extra one with one endpoint at $x$ which might have length less than $K$. If the subtree can be partitioned, this function will return the maximum possible length of the extra path. Otherwise, the function will return $-1$, meaning that it is impossible to divide the tree.

First, we should call $DFS(t)$ for all children $t$ of $x.$ If any of these return $-1,$ then $DFS(x)$ should also return $-1.$ Otherwise, we have a path of length $DFS(t)+1$ with one endpoint at $x.$

Suppose that we want to check whether we can pair up all the child paths of $x$ such that all paths have length at least $K$. To do this, sort the path lengths in increasing order and repeatedly pair the least and the greatest lengths. If there are an odd number of path lengths, we should add $0$ to the beginning of this list before pairing.

Otherwise, one child path will be left unpaired, and we would like to maximize the length of this path. Note that if it is possible to end up with an extra path of length $x,$ then for all $y<x$ it is also possible to end up with an extra path of length $y.$ Thus, we can binary search again to find the maximum possible $x.$

In summary, $DFS(x)$ will return the maximum possible length of an extra path if possible. Otherwise, if we can pair up all child paths, $DFS(x)$ will return $0.$ Otherwise, it is not possible to generate paths such that all have length at least $K,$ so $DFS(x)$ should return $-1.$

This solution runs in $O(N\log^2N)$ time.

#include "bits/stdc++.h"

using namespace std;

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 

#define f first
#define s second

const int MOD = 1e9+7;
const int MX = 1e5+5;

int N,K;
vector<int> adj[MX];
bool bad = 0;
bool ok(const vector<int>& V, int mid) {
	int l = 0, r = (int)V.size()-1;
	for (int i = 0; i < V.size()/2; ++i) {
		if (l == mid) l ++;
		if (r == mid) r --;
		if (V[l]+V[r] < K) return 0;
		l ++, r --;
	return 1;
int DFS(int x, int y) {
	if (bad) return -1;
	vector<int> v; 
	for (auto t: adj[x]) if (t != y) {
		int d = DFS(t,x)+1; if (bad) return -1;
	bool al = 1;
	int mx = -MOD;
		auto V = v; if (V.size()&1) V.insert(V.begin(),0);
		al = ok(V,-1);
		auto V = v; if (!(V.size()&1)) V.insert(V.begin(),0);
		int lo = -1, hi = V.size()-1;
		while (lo < hi) {
			int mid = (lo+hi+1)/2;
			if (ok(V,mid)) lo = mid;
			else hi = mid-1;
		if (lo >= 0) mx = V[lo];
	if (x == 1) {
		if (!al) bad = 1;
		return -1;
	if (mx != -MOD) return mx;
	if (al) return 0;
	bad = 1; return -1;
bool SOLVE(int k) {
	K = k; bad = 0; DFS(1,0);
	return !bad;
void SOLVE() {
	int lo = 1, hi = N-1;
	while (lo < hi) {
		int mid = (lo+hi+1)/2;
		if (SOLVE(mid)) lo = mid;
		else hi = mid-1;
	cout << lo << "\n";
int main() {
	// setIO(); 
	cin >> N;
	for (int i = 1; i < N; ++i) {
		int a,b; cin >> a >> b;
		adj[a].push_back(b), adj[b].push_back(a);