题目链接
翻译
让你构造一棵树，使得任意两个叶子节点之间路径的权重异或和为 (0)。
并且，树中用到的边的权重的不同值的个数设为 (f)，让你求 (f) 的最大值和最小值。
题解
最小值不会超过 (3)。
可以转化为是在给每个点标记数字，然后边上的权重就是连接它们两个点上标的数字的异或值。
这样的话，只要保证任意两个叶子节点上标记的数字是一样的，就能满足题意了。
我们可以把所有的叶子都标记上 (1)，然后中间的非叶子节点标记上 (2) 或 (3) (因为权重要大于 (0)，所以相邻两个节点权重不能相同)。
可以想见，如果只用 (1) 和 (2) 就能让树上相邻两个点数字不同(且叶子节点数字都相同)，那么只会产生一种边权，最小答案就可以为 (1)，否则 (3)
个数字，两两异或最多组成 (3) 种权重。因此最小答案的最大值就为 (3)。
关于等于 (1) 的判断，可以选择一个叶子节点作为根进行 (dfs) 然后求出它到其他叶子节点的距离，如果满足这些到叶子节点的距离都为偶数。那么就可以
为 (1)，因为任意两个节点的树上距离为 (dis(x,root)+dis(y,root)-2*dis(lca(x,y),root))。
对于最大值的情况，显然只要让边权为 (2^0,2^1,2^2....) 然后和叶子节点连接的那个边权等于前面这些数字的和就好了,即二进制全为 (1)。
这样的话，理想情况下我们所有边的边权都可以不同。
但是理想是丰满的，现实是残酷的。对于连在同一个节点上的两个叶子节点，它们俩和这个节点的边权必然是相同的，所以要减掉。
直接给结论吧，最大值为 (n-1-cntLeaf+cntSpecial) 这里的 (cntSpecial) 是所有和叶子节点有连接的点的个数。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5;
int n;
int du[N+10],dis[N+10];
vector<int> g[N+10];
//[6]写dfs
void dfs(int x,int fa){
for (int y:g[x]){
if (y==fa){
continue;
}
//[7]统计到这个点的距离
dis[y] = dis[x] + 1;
dfs(y,x);
}
}
int main(){
// freopen("C://1.cppSourceProgram//rush.txt","r",stdin);
ios::sync_with_stdio(0),cin.tie(0);
//step1 输入数据
cin >> n;
for (int i = 1;i <= n-1; i++){
int x,y;
cin >> x >> y;
//step2 统计度信息
du[x]++;du[y]++;
// 5 简图
g[x].push_back(y);
g[y].push_back(x);
}
//step3 找个度为 1 的叶子当根
int root = 1;
for (int i = 2;i <= n; i++){
if (du[i] == 1){
root = i;
}
}
//step4 从root 开始做 dfs
dfs(root,-1);
int mi = 1;
//[8]看看是不是到所有叶子节点的距离都为偶数
for (int i = 1;i <= n; i++){
if (dis[i]%2!=0 && du[i] == 1){
mi = 3;
}
}
cout << mi <<" ";
//[9] 找和叶子节点相邻的节点数目
int cnt1 = 0;
//[10] 叶子节点数
int cntLeaf = 0;
for (int i = 1;i <= n; i++){
if (du[i] == 1){
cntLeaf++;
}
int ok = 0;
for(int y:g[i]){
if (du[y] == 1){
ok=1;
}
}
cnt1+=ok;
}
// [11] math
int ma = n - 1 - cntLeaf + cnt1;
cout << ma << endl;
return 0;
}