Description：

求一棵树的最小不相交路径覆盖和最小路径覆盖的最小的最长路径长度。

$1\leqslant n\leqslant 10^4$

Solution：

第一问比较简单，如果有奇数个子树，就两两合并，留一个向上走，否则新开一个。

对于第二问，可以先二分最小路径长度，然后对每一个子树求 $f[i]$ 表示这个子树在路径覆盖最小的前提下向上延伸的那个最短是多少，每次把所有子节点的 $f$ 值拿出来排序，如果有偶数个就加一个 $0$ 表示开始的，那么如果能两两配对最后剩一个，且每个配对长度和都不大于限制，那么就可以把最后剩的那个向上传递，根据贪心的思路我们肯定要把一个尽量小的留给上面我们可以把所有子树的 $f[i]+1$ 拿出来排序，然后二分最后向上传递的那个，之所以可以二分是因为如果存在一种方案大的能向上传递那么小的一定也能，然后判断一下就好了，注意如果有一个 $f+1\geqslant \text{limit}$ 应直接返回 $\text{false}$ 。

注意根节点的特殊情况。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 10010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

bool v[MAXN];

int dp1(int k)

{

	v[k] = true;

	int s = 0,sum = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		sum += dp1(e[i].to);

		++s;

	}

	sum -= s / 2;

	if(s % 2 == 0 && k != 1)++sum;

	return sum;

}

int f[MAXN];

int s[MAXN],top = 0;

#define INF 0x3f3f3f3f

int g[MAXN],tot = 0;

bool check(int k,int lim)

{

	tot = 0;

	for(int i = 1;i <= top;++i)

	{

		if(i == k)continue;

		g[++tot] = s[i];

	}

	for(int i = 1,j = tot;i < j;++i,--j)

	{

		if(g[i] + g[j] > lim)return false;

	}

	return true;

}

bool dp2(int k,int lim)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		if(!dp2(e[i].to,lim))return false;

	}

	top = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		s[++top] = f[e[i].to] + 1;

	}

	v[k] = false;

	if(top % 2 == 0 && k != 1)s[++top] = 0;

	sort(s + 1,s + 1 + top);

	if(s[top] > lim)return false;

	if(k == 1)return check(0,lim);

	int l = 1,r = top,mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(check(mid,lim))r = mid;

		else l = mid + 1;

	}

	if(!check(l,lim))return false;

	f[k] = s[l];

	return true;

}

int main()

{

	scanf("%d",&n);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	int ans = dp1(1);

	int l = 1,r = n,mid;

	memset(v,false,sizeof(v));

	while(l < r)

	{

		memset(v,false,sizeof(v));

		mid = ((l + r) >> 1);

		if(dp2(1,mid))r = mid;

		else l = mid + 1;

	}

	cout << ans << " " << l << endl;

	return 0;

}