【深度优先搜索 图论 树】2872. 可以被 K 整除连通块的最大数目

class CNeiBo
{
public: 
  static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
  {
    vector<vector<int>>  vNeiBo(n);
    for (const auto& v : edges)
    {
      vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
      if (!bDirect)
      {
        vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
      }
    }
    return vNeiBo;
  } 
  static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
  {
    vector<vector<std::pair<int, int>>> vNeiBo(n);
    for (const auto& v : edges)
    {
      vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
      if (!bDirect)
      {
        vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
      }
    }
    return vNeiBo;
  }
  static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext)
  {
    vector<vector<int>> vNeiBo(rCount * cCount);
    auto Move = [&](int preR, int preC, int r, int c)
    {
      if ((r < 0) || (r >= rCount))
      {
        return;
      }
      if ((c < 0) || (c >= cCount))
      {
        return;
      }
      if (funVilidCur(preR, preC) && funVilidNext(r, c))
      {
        vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c);
      }
    };
    for (int r = 0; r < rCount; r++)
    {
      for (int c = 0; c < cCount; c++)
      {
        Move(r, c, r + 1, c);
        Move(r, c, r - 1, c);
        Move(r, c, r, c + 1);
        Move(r, c, r, c - 1);
      }
    }
    return vNeiBo;
  }
  static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
  {
    vector<vector<int>> neiBo(neiBoMat.size());
    for (int i = 0; i < neiBoMat.size(); i++)
    {
      for (int j = i + 1; j < neiBoMat.size(); j++)
      {
        if (neiBoMat[i][j])
        {
          neiBo[i].emplace_back(j);
          neiBo[j].emplace_back(i);
        }
      }
    }
    return neiBo;
  }
};
class Solution {
public:
  int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) {
    m_values = values;
    m_iK = k;
    auto neiBo = CNeiBo::Two(n, edges, false);
    DFS(neiBo, 0, -1);
    return m_iRet+1;
  }
  long long DFS(vector<vector<int>>& neiBo, int cur, int par)
  {
    long long llSum = m_values[cur];
    for (const auto& next : neiBo[cur])
    {
      if (next == par)
      {
        continue;
      }
      llSum += DFS(neiBo, next, cur);
    }
    if ((0 == llSum % m_iK)&&( 0 != cur)) { m_iRet++; }
    return llSum;
  }
  vector<int> m_values;
  int m_iK;
  int m_iRet = 0;
};