【树】【异或】【深度优先】【DFS时间戳】2322. 从树中删除边的最小分数

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);
  }
}