思路：树形DP。先求最大值。
令s[x]为x的子树中叶子节点的数量。
f[x]为到x时 为先手走，先手能取到的值在子树中排第f[x]小。
g[x]为到x时 为后手走，后手能取到的值在子树中排第f[x]小。
对f[x]，先手应该往哪个子树走呢?对于x的一棵子树y，如果进入，那么最终答案就是这棵子树中第g[y]小的值，即第s[y]-g[y]大的值，那么先手只要找到s[y]-g[y]最小的一棵子树，然后用最大的s[y]-g[y]个编号填好这s[y]-g[y]点，那么f[i]=s[i]-(s[y]-g[y])；
对于g[x]，情况就有些不同了，对于x的一棵子树y，如果进入，那么会得到第f[y]小的值，因为现在是求最大，所以这棵子树中的s[y]-f[y]个点会被最大化以使第f[y]小的值尽量大。最终答案就是所有子树的第f[y]小值中的最小值。
最小化同理
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010,maxm=400010;
int now[maxn],pre[maxm],son[maxm],n,tot,s[maxn],f[maxn][2],g[maxn][2];
void add(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
void dfs(int x){
if (!now[x]){f[x][0]=f[x][1]=g[x][0]=g[x][1]=s[x]=1;return;}
s[x]=0,g[x][1]=1e9;int s1=0,s2=0;
for (int y=now[x];y;y=pre[y]) dfs(son[y]),s[x]+=s[son[y]];
for (int y=now[x];y;y=pre[y]){
f[x][0]=max(f[x][0],s[x]-s[son[y]]+g[son[y]][0]);
g[x][1]=min(g[x][1],f[son[y]][1]);
s1+=s[son[y]]-f[son[y]][0]+1,s2+=g[son[y]][1];
}
g[x][0]=s[x]-s1+1,f[x][1]=s2;
}
int main(){
scanf("%d",&n);
for (int i=1,a,b;i<n;i++) scanf("%d%d",&a,&b),add(a,b);
dfs(1);printf("%d %d
",f[1][0],f[1][1]);
return 0;
}