作者推荐
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
涉及知识点
树 异或 DFS时间戳
LeetCode2322. 从树中删除边的最小分数
存在一棵无向连通树，树中有编号从 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 小的删除边方案。
示例 2：
输入：nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
输出：0
解释：上图展示了一种删除边方案。
- 第 1 个组件的节点是 [3,4] ，值是 [4,4] 。异或值是 4 ^ 4 = 0 。
- 第 2 个组件的节点是 [1,0] ，值是 [5,5] 。异或值是 5 ^ 5 = 0 。
- 第 3 个组件的节点是 [2,5] ，值是 [2,2] 。异或值是 2 ^ 2 = 0 。
分数是最大异或值和最小异或值的差值，0 - 0 = 0 。
无法获得比 0 更小的分数 0 。
提示：
n == nums.length
3 <= n <= 1000
1 <= nums[i] <= 108
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一棵有效的树
预备知识
性质一：n个数进行异或运算。各位的结果等于各数本位1的数量是否为奇数。
当前 n 为 2 时：只有四种情况 1 ⊕ 1 = 0 , 0 ⊕ 0 = 0 , 0 ⊕ 1 = 1 , 1 ⊕ 0 = 1 全部符合 当 n > 2 时，任意选两个数，运算后 1 的数量奇偶性不变 当前n为2时：只有四种情况1\oplus1= 0, 0\oplus0= 0, 0\oplus1= 1,1\oplus0= 1 全部符合 \\ 当n>2时，任意选两个数，运算后1的数量奇偶性不变 当前n为2时：只有四种情况1⊕1=0,0⊕0=0,0⊕1=1,1⊕0=1全部符合当n>2时，任意选两个数，运算后1的数量奇偶性不变
推论一： n个数的异或，结果与运算顺序无关。
推论二：异或的逆运算就是本身。
深度优先
以任意节点（比如0）为根,除根节点外，每个节点都有且只有一个父节点。枚举两个非根节点A,B,A ≠ \neq =B。设整个树的的异或值c，子树A、B的异或值分别为a,b。删除后A和B连向父节点的边，0节点为根的树、A节点为根的树、B节点为根的树的异或值分别为：
{ c ⊕ a , a ⊕ b ， b a 是 b 祖先 c ⊕ b ， a , b ⊕ a b 是 a 祖先 c ⊕ a ⊕ b , a , b o t h e r \begin{cases} c \oplus a ,a\oplus b， b & a是b祖先 \\ c \oplus b， a ,b \oplus a & b是a祖先 \\ c\oplus a \oplus b,a,b & other \\ \end{cases} ⎩ ⎨ ⎧c⊕a,a⊕b，bc⊕b，a,b⊕ac⊕a⊕b,a,ba是b祖先b是a祖先other
一，DFS各子树的异或值，祖先后代关心，时间复杂度O(nn)。
二，枚举两个节点（边），时间复杂度O(nn)。
代码
核心代码
class CNeiBo2
{
public:
CNeiBo2(int n, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase)
{
m_vNeiB.resize(n);
}
CNeiBo2(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase)
{
m_vNeiB.resize(n);
for (const auto& v : edges)
{
m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase);
if (!bDirect)
{
m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase);
}
}
}
inline void Add(int iNode1, int iNode2)
{
iNode1 -= m_iBase;
iNode2 -= m_iBase;
m_vNeiB[iNode1].emplace_back(iNode2);
if (!m_bDirect)
{
m_vNeiB[iNode2].emplace_back(iNode1);
}
}
const int m_iN;
const bool m_bDirect;
const int m_iBase;
vector<vector<int>> m_vNeiB;
};
class Solution {
public:
int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
m_c = nums.size();
CNeiBo2 neiBo(m_c, edges, false);
m_vXor.resize(m_c);
m_vParent.assign(m_c, vector<bool>(m_c));
vector<int> parent;
DFS1(neiBo.m_vNeiB, 0, -1, nums, parent);
int iRet = INT_MAX;
int v[3];
for (int i = 1; i < m_c; i++)
{
for (int j = 1; j < m_c; j++)
{
if (i == j)
{
continue;
}
if (m_vParent[i][j])
{
v[0]=(m_vXor[0] ^ m_vXor[j]);
v[1] = (m_vXor[i]);
v[2] = (m_vXor[j] ^ m_vXor[i]);
}
else if(m_vParent[j][i])
{
v[0] = (m_vXor[0] ^ m_vXor[i]);
v[1] = (m_vXor[i]^ m_vXor[j]);
v[2] = ( m_vXor[j]);
}
else
{
v[0] = (m_vXor[0] ^ m_vXor[i] ^ m_vXor[j]);
v[1] = (m_vXor[i]);
v[2] = (m_vXor[j]);
}
sort(v, v+3);
iRet = min(iRet, v[2] - v[0]);
}
}
return iRet;
}
int DFS1(vector<vector<int>>& neiBo, int cur, int par, const vector<int>& nums, vector<int>& parent)
{
int ret = nums[cur];
for (const auto& par1 : parent)
{
m_vParent[cur][par1] = true;
}
parent.emplace_back(cur);
for (const auto& next : neiBo[cur])
{
if (next == par)
{
continue;
}
ret ^= DFS1(neiBo, next, cur, nums, parent);
}
parent.pop_back();
return m_vXor[cur]=ret;
}
vector<int> m_vXor;
vector<vector<bool>> m_vParent;
int m_c;
};
测试用例
template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
vector<int> nums;
vector<vector<int>> edges;
{
Solution sln;
nums = { 1,5,5,4,11 }, edges = { {0,1},{1,2},{1,3},{3,4} };
auto res = sln.minimumScore(nums, edges);
Assert(9, res);
}
{
Solution sln;
nums = { 5,5,2,4,4,2 }, edges = { {0,1},{1,2},{5,2},{4,3},{1,3} };
auto res = sln.minimumScore(nums, edges);
Assert(0, res);
}
}
利用时间戳优化
已处理的节点中，时间戳大于cur的节点 是后代。两个变量分别记录：cur的时间戳，dfs(cur)结束时的时间戳。
2023年4月
class Solution {
public:
int minimumScore(vector& nums, vector<vector>& edges) {
m_c = nums.size();
m_vNeiB.resize(m_c);
m_vLeve.resize(m_c);
m_vXORSum.resize(m_c);
m_vInTime.resize(m_c);
m_vOutTime.resize(m_c);
m_nums = nums;
for (const auto& v : edges)
{
m_vNeiB[v[0]].emplace_back(v[1]);
m_vNeiB[v[1]].emplace_back(v[0]);
}
dfs(0, -1);
int iRet = INT_MAX;
std:vector v(3);
for (int i = 0; i < edges.size(); i++)
{
int iChild1 = (m_vLeve[edges[i][0]] > m_vLeve[edges[i][1]]) ? edges[i][0] : edges[i][1];
for (int j = i + 1; j < edges.size(); j++)
{
int iChild2 = (m_vLeve[edges[j][0]] > m_vLeve[edges[j][1]]) ? edges[j][0] : edges[j][1];
if (IsGrandParent(iChild1, iChild2))
{
v[0] = (m_vXORSum[iChild2] ^ m_vXORSum[iChild1]);
v[1] = (m_vXORSum[iChild1]);
v[2] = (m_vXORSum[0] ^ m_vXORSum[iChild1] ^ m_vXORSum[iChild2] ^ m_vXORSum[iChild1]);
}
else if (IsGrandParent(iChild2, iChild1))
{
v[0] = (m_vXORSum[iChild1] ^ m_vXORSum[iChild2]);
v[1] = (m_vXORSum[iChild2]);
v[2] = (m_vXORSum[0] ^ m_vXORSum[iChild1] ^ m_vXORSum[iChild2] ^ m_vXORSum[iChild2]);
}
else
{
v[0] = (m_vXORSum[iChild1]);
v[1] = (m_vXORSum[iChild2]);
v[2] = (m_vXORSum[0] ^ m_vXORSum[iChild1] ^ m_vXORSum[iChild2]);
}
const int iCurRet = *std::max_element(v.begin(), v.end()) - *std::min_element(v.begin(), v.end());
iRet = min(iRet, iCurRet);
}
}
return iRet;
}
bool IsGrandParent(int iNode1, int iIsGrandParent)
{
return (m_vInTime[iIsGrandParent] < m_vInTime[iNode1]) && (m_vOutTime[iIsGrandParent] >= m_vOutTime[iNode1]);
}
void dfs(int iCur, int iParent)
{
m_vInTime[iCur] = m_iTime++;
m_vLeve[iCur] = (-1 == iParent) ? 0 : m_vLeve[iParent]+1 ;
int iXorSum = m_nums[iCur];
for (const auto& next : m_vNeiB[iCur])
{
if (next == iParent)
{
continue;
}
dfs(next, iCur);
iXorSum ^= m_vXORSum[next];
}
m_vXORSum[iCur] = iXorSum;
m_vOutTime[iCur] = m_iTime;
}
int m_c;
vector<vector> m_vNeiB;
vector m_vLeve, m_vInTime, m_vOutTime;;
vector m_vXORSum;
vector m_nums;
int m_iTime = 1;
};
