首先我们要有一个明确的构造思路
对于非根节点，我们把子树连上来的线两两配对，这样如果它有奇数个子树就会剩一个，这时候把这根线传给父亲即可。对于根节点还是两两配对，但是注意如果它也有奇数个子树就不能剩了，必须把这根线算上。这样第一问的答案就是每个非根节点贡献度数除以二下取整，根节点贡献度数除以二上取整
第二问我们先二分答案，仍然沿用这个思路，这时我们要让最长的最短，于是我们每次把子树里传上来的线塞进一个multiset。讨论：对于有奇数个子树的情况，从大到小枚举线，二分出和当前的线拼起来不超过二分的$mid$的最长的线，然后把它们删掉，最后剩下的那根传给父亲。注意如果有一根线找不到配对也不一定失败，我们先视为把它传给父亲，然后看看剩下的还能不能拼好。对于有偶数个子树的情况，我们直接塞一个零进multiset里去，然后按奇数的方法做，这是等价的。对于根节点，我们去除掉塞零和留线这两个操作判定即可。
#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int p[N],noww[*N],goal[*N],deg[N],dp[N];
int n,t1,t2,cnt,mins,l,r,mid,ans;
multiset<int> se;
multiset<int>::iterator it;
void link(int f,int t)
{
noww[++cnt]=p[f];
goal[cnt]=t,p[f]=cnt;
}
bool check(int nde,int fth)
{
if(deg[nde]==&&nde!=)
{dp[nde]=; return true;}
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth&&!check(goal[i],nde))
return false;
se.clear();
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth)
se.insert(dp[goal[i]]+);
if(nde==)
{
while(se.size()>)
{
long long mem=*(--se.end());
se.erase(--se.end()); it=se.upper_bound(mid-mem);
if(it!=se.begin()) it--; else return false;
if((*it)+mem>mid) return false; se.erase(it);
}
if(se.size()) return (*se.begin())<=mid;
else return true;
}
else
{
int must=;
if(se.size()%==) se.insert();
while(se.size()>)
{
long long mem=*(--se.end());
se.erase(--se.end()); it=se.upper_bound(mid-mem);
if(it!=se.begin()) it--; else return false;
if((*it)+mem>mid)
{
if(must) return false;
else
{
must=*(--se.end());
continue;
}
}
else se.erase(it);
}
return (dp[nde]=must?must:(*se.begin()))<=mid;
}
return true;
}
int main ()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d%d",&t1,&t2);
link(t1,t2),link(t2,t1);
deg[t1]++,deg[t2]++;
}
mins+=(deg[]+)/;
for(int i=;i<=n;i++)
mins+=(deg[i]-)/;
l=,r=n;
while(l<=r)
{
mid=(l+r)/;
if(check(,)) r=mid-,ans=mid;
else l=mid+;
}
printf("%d %d",mins,ans);
return ;
}