这个题目有些意思，可以给我们一些启发，题目如下，
存在一棵无向连通树，树中有编号从 0 到 n - 1 的 n 个节点， 以及 n - 1 条边。
给你一个下标从 0 开始的整数数组 nums ，长度为 n ，其中 nums[i] 表示第 i 个节点的值。另给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中存在一条位于节点 ai 和 bi 之间的边。
删除树中两条 不同 的边以形成三个连通组件。对于一种删除边方案，定义如下步骤以计算其分数：
分别获取三个组件 每个 组件中所有节点值的异或值。
最大 异或值和 最小 异或值的 差值 就是这一种删除边方案的分数。
例如，三个组件的节点值分别是：[4,5,7]、[1,9] 和 [3,3,3] 。三个异或值分别是 4 ^ 5 ^ 7 = 6、1 ^ 9 = 8 和 3 ^ 3 ^ 3 = 3 。最大异或值是 8 ，最小异或值是 3 ，分数是 8 - 3 = 5 。
返回在给定树上执行任意删除边方案可能的 最小 分数。
示例 1：
输入：nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
输出：9
解释：上图展示了一种删除边方案。
- 第 1 个组件的节点是 [1,3,4] ，值是 [5,4,11] 。异或值是 5 ^ 4 ^ 11 = 10 。
- 第 2 个组件的节点是 [0] ，值是 [1] 。异或值是 1 = 1 。
- 第 3 个组件的节点是 [2] ，值是 [5] 。异或值是 5 = 5 。
分数是最大异或值和最小异或值的差值，10 - 1 = 9 。
可以证明不存在分数比 9 小的删除边方案。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
把一个树去掉2条边，求得到的3个部分的一个函数值，
一个思路：固定0号节点为根节点，然后枚举要去掉的2条边，这个时候，需要判断2条边的关系，是否存在直系关系，可以考虑记录高度（层次），再一层层的回溯，判断是不是直系，
这个方法会超时，代码如下，
struct node {
int id;
int h;
node* pre;
// vector<node*> nts;//nexts
int val;//store data
node() {
h = 10000;
}
};
class Solution {
public:
int getv(int a, int b, int c) {
int mx = max(a, max(b, c));
int mi = min(a, min(b, c));
return mx - mi;
}
map<int, vector<int>> ve;
int dfs(int id, vector<int>& nums, int ih, vector<node>& nds) {
nds[id].h = ih;
nds[id].id = id;
vector<int>& con = ve[id];
int t = nums[id];
for (int i = 0; i < con.size(); i++) {
int cid = con[i];
if (nds[cid].h < ih) continue;
nds[cid].pre = &nds[id];
t ^= dfs(cid, nums, ih+1, nds);
}
nds[id].val = t;
return t;
}
int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
//init the edges by v
for (auto& v: edges) {
int v0 = v[0];
int v1 = v[1];
ve[v0].push_back(v1);
ve[v1].push_back(v0);
}
//get score for each v as root
int len = nums.size();
vector<node> nds(len);
dfs(0, nums, 0, nds);
// vector<vector<node*>> lay;//layer
// nds[0].id = 0;
// lay.push_back({&nds[0]});
int all = nds[0].val;
// int mx = all; all may be very little, it is wrong to use all as mx at beginning
int mx = 1000000000;
int k, t, vhi, vhj;
for (int i = 1; i < len; i++) {
for (int j = i+1; j < len; j++) {
int hi = nds[i].h;
int hj = nds[j].h;
if (hi == hj) {
vhi = nds[i].val;
vhj = nds[j].val;
k = all ^ vhi ^ vhj;
} else if (hi < hj) {
int a = hj;
node* p = &nds[j];
while (p->h > nds[i].h) {
p = p->pre;
}
if (p->id == i) {
vhj = nds[j].val;
k = all ^ nds[i].val;
vhi = nds[i].val ^ vhj;
} else {
vhi = nds[i].val;
vhj = nds[j].val;
k = all ^ vhi ^ vhj;
}
} else if (hi > hj) {
int a = hi;
node* p = &nds[i];
while (p->h > nds[j].h) {
p = p->pre;
}
if (p->id == j) {
vhi = nds[i].val;
k = all ^ nds[j].val;
vhj = nds[j].val ^ vhi;
} else {
vhi = nds[i].val;
vhj = nds[j].val;
k = all ^ vhi ^ vhj;
}
}
t = getv(k, vhi, vhj);
mx = min(mx, t);
}
}
return mx;
}
};判断是否直系的时候会花些时间，这里可以考虑空间换时间，使用hash方法存储一下每个节点的后代节点，就可以快速查找判断了，代码如下：
struct node {
int id;
int h;
// node* pre;
// vector<node*> nts;//nexts
int val;//store data
node() {
h = 10000;
}
};
class Solution {
public:
int getv(int a, int b, int c) {
int mx = max(a, max(b, c));
int mi = min(a, min(b, c));
return mx - mi;
}
map<int, vector<int>> ve;
int dfs(int id, vector<int>& nums, int ih, vector<node>& nds, vector<vector<int>>& kds, vector<vector<int>>& hash) {
nds[id].h = ih;
nds[id].id = id;
vector<int>& con = ve[id];
int t = nums[id];
kds[id].push_back(id);
for (int i = 0; i < con.size(); i++) {
int cid = con[i];
if (nds[cid].h < ih) continue;
t ^= dfs(cid, nums, ih+1, nds, kds, hash);
for (auto& v : kds[cid]) {
kds[id].push_back(v);
hash[id][v] = 1;
}
}
nds[id].val = t;
return t;
}
int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
//init the edges by v
for (auto& v: edges) {
int v0 = v[0];
int v1 = v[1];
ve[v0].push_back(v1);
ve[v1].push_back(v0);
}
//get score for each v as root
int len = nums.size();
vector<node> nds(len);
vector<vector<int>> kids(len);
vector<vector<int>> hash(len, vector<int>(len, 0));
dfs(0, nums, 0, nds, kids, hash);
int all = nds[0].val;
// int mx = all; all may be very little, it is wrong to use all as mx at beginning
int mx = 1000000000;
int k, t, vhi, vhj;
for (int i = 1; i < len; i++) {
for (int j = i+1; j < len; j++) {
vhi = nds[i].val;
vhj = nds[j].val;
if (hash[i][j] == 1) {
k = all ^ vhi;
vhi = vhi ^ vhj;
} else if (hash[j][i] == 1) {
k = all ^ vhj;
vhj = vhj ^ vhi;
} else {
k = all ^ vhi ^ vhj;
}
t = getv(k, vhi, vhj);
mx = min(mx, t);
}
}
return mx;
}
};
其实还有更好的方法，考虑另外一个问题：从一个树结构中选择2个节点，判断这2个节点是不是直系关系。
我们通过树的前序遍历栈处理来查看，一个节点push和pop的操作过程中的其他节点，就是该节点的后代节点，通过这样的标记，我们就可以来判断。使用dfs遍历也可以这样标记，
可参考
该题的另外一个方法，很巧妙，把2条要删除的边结构，构造到一个树结构中，认定是直系关系，同时其中1条边作为根节点上的边，这样就只需要枚举另外一个边了，直接从后代节点中查找。
参考
力扣
https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/solution/by-newhar-imbx/