分析

没错还是构造……

明确某个数异或另一个数偶数次，结果仍然是它本身。

再明确所有的数字都是正整数，不能用 \(0\)。

任意两个叶子之间的路径权值的异或和为 \(0\)，如果它们之间的距离是偶数的话，那么都填同一个数就好了。最小数量为 \(1\)。

如果存在某两个叶子之间的距离不为偶数，如下图 \(1\) 和 \(5\)。

钦定 \((1 \rightarrow 3)\) 的权值为 \(39\)，那么如果 \((3 \rightarrow 4)\) 或者 \((4 \rightarrow 5)\) 任何一个是 \(39\)，\(39 \operatorname{xor} 39 =0\)，结果都是另一条边的权值。所以假如 \((4 \rightarrow 5)\) 是 \(815\)，那么 \((3 \rightarrow 4)\) 只有是 \(39 \operatorname{xor} 815=776\) 才能满足异或和为 \(0\)。

其实这就相当于把两条边「合并」为一条边，权值为它们的异或值，这样奇数距离就转化成了偶数。至于更长的奇数距离的情况，依旧这样去做，不难发现这种情况下最少使用 \(3\) 种权值。

那么最多呢？直接做不好想，考虑从它的补集入手。如果没有任何限制，那么一定是每一条边一个权值，共有 \((n-1)\) 种。然后再减去会「因为某些边权的确定而被动确定的边」就行了。

依旧是上图，假如上述权值不变，那么 \((2 \rightarrow 3)\) 能够填什么呢？\((1 \rightarrow 5)\) 和 \((2 \rightarrow 5)\)，在 \((3 \rightarrow 5)\) 这一段是重叠的，只有 \((2 \rightarrow 3)\) 的权值与 \((1 \rightarrow 3)\) 相同，才能让异或和为 \(0\)。不难发现，对于同一个父亲的叶子节点，它们与父亲之间的边只能是一种。假如一个点 \(x\) 有 \(t_x\) 个叶子节点，其中 \(t_x-1\) 条边的权值一定是与剩下那一条相同的。

综上所述，权值最多的情况，就是 \[ n-1 - \sum_{x \in V \text{ and } t_x \ge 1} t_x -1 \] 注意如果 \(t_x=1\)，贡献是 \(0\)，如果 \(t_x=0\) 也没有贡献。

 

因为是无根树，所以要钦定根节点。

对于寻找最小数量，可以找到一个叶子节点作为根，判断它到其他叶子节点的距离是否都是偶数，是的话答案为 \(1\)，否则为 \(3\)。因为树的奇妙性质所以不会存在某个叶子和另一个叶子到「根」的距离是偶数，但是它们之间的距离是奇数的问题。

在寻找最大值时，如果还从叶子节点开始搜索的话会产生遗漏，所以从以一个非叶子节点为根，统计 \(t_x\)。

CODE

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n, sum;
int tot, h[N], to[N<<1], nxt[N<<1];
bool flag=1;
void add(int x,int y) { to[++tot]=y, nxt[tot]=h[x], h[x]=tot; }
int read() {
    int a=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a;
}
void dfs1(int x,int fa,int dis) {
    if(!nxt[h[x]]&&dis&1) flag=0;
    // 与某个叶子节点距离为奇数
    for(int i=h[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==fa) continue;
        dfs1(y,x,dis+1);
    }
}
void dfs2(int x,int fa) {
    int t=0;
    for(int i=h[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==fa) continue;
        dfs2(y,x);
        t+=!nxt[h[y]];
        // !nxt[h[y]]=1，叶子
    }
    if(t) sum+=t-1;
}
int main() {
    n=read();
    if(n==2) { puts("1 1"); return 0; }
    for(int i=1;i<n;++i) {
        int x=read(), y=read();
        add(x,y), add(y,x);
    }
    int root=0;
    for(int i=1;!root&&i<=n;++i) if(!nxt[h[i]]) root=i;
    // 叶子节点
    dfs1(root,0,0);
    root=0;
    for(int i=1;!root&&i<=n;++i) if(nxt[h[i]]) root=i;
    // 非叶子节点
    dfs2(root,0);
    printf("%d %d\n",flag? 1:3,n-sum-1);
}