【树上倍增】【内向基环树】【 图论 】2836. 在传球游戏中最大化函数值

class CPow2
{
public:
  CPow2(vector<int>& receiver, long long k): m_c(receiver.size())
  {
    long long tmp = k;
    int iPow2 = 0;
    for( ; iPow2 <= 63;iPow2++ )
    {
      if ((1LL << iPow2) == tmp)
      {
        break;
      }
      tmp &= ~(1LL << iPow2);
    }
    m_vParent.assign(iPow2 + 1, vector<int>(m_c));
    m_vSum.assign(iPow2 + 1, vector<long long>(m_c));
    for (int i = 0; i < m_c; i++)
    {
      m_vParent[0][i] = receiver[i];
      m_vSum[0][i] =  receiver[i];
    }
    for (int j = 1; j <= iPow2; j++)
    {
      for (int i = 0; i < m_c; i++)
      {
        const int next = m_vParent[j - 1][i];
        m_vParent[j][i] = m_vParent[j - 1][next];
        m_vSum[j][i] = m_vSum[j-1][i] + m_vSum[j-1][next];
      }
    }
  }
  long long Query(int cur, long long k)
  {
    long long ans = 0;
    for (int i = 0; i < m_vParent.size(); i++)
    {
      if ((1LL << i) & k)
      {
        ans += m_vSum[i][cur];
        cur = m_vParent[i][cur];
      }
    }
    return ans;
  }
  const int m_c;
protected:  
  vector<vector<int>> m_vParent;
  vector<vector<long long>> m_vSum;
};
class Solution {
public:
  long long getMaxFunctionValue(vector<int>& receiver, long long k) {
    CPow2 pow(receiver, k);
    long long llMax = 0;
    for (int i = 0; i < pow.m_c; i++)
    {
      llMax = max(llMax, i+pow.Query(i, k));
    }
    return llMax;
  }
};

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> receiver; long long k;
  {
    Solution sln;
    receiver = { 1,0 }, k = 10000000000;
    auto res = sln.getMaxFunctionValue(receiver, k);
    Assert(5000000001, res);
  }
  {
    Solution sln;
    receiver = { 2, 0, 1 }, k = 4;
    auto res = sln.getMaxFunctionValue(receiver, k);
    Assert(6, res);
  }
  {
    Solution sln;
    receiver = { 1,1,1,2,3 }, k =3;
    auto res = sln.getMaxFunctionValue(receiver, k);
    Assert(10, res);
  }
}

//求各点到环上的次数，及距离
  m_vDisScoreToCycle.assign(m_c, std::make_tuple(- 1,-1,-1));
  for (int i = 0; i < m_c; i++)
  {
    dfs(i);
  }
  m_vRet.assign(m_c,-1);
  CCycle cycle(receiver);
  cycle.Init(m_setNotCycle);
  //处理整个路径都在环上
  for (int i = 0; i < m_c; i++)
  {
    if (m_setNotCycle.count(i))
    {
      continue;
    }   
    m_vRet[i] = cycle.CalScore(i, k);
  }
  //处理整个路径不在环上的点
  for (const auto cur : m_setInDeg0)
  {
    dfsLen(cur, k);
  }
  //非环开始，环结束
  for (int i = 0; i < m_c; i++)
  {
    if (-1 != m_vRet[i])
    {
      continue;
    }
    m_vRet[i] = get<1>(m_vDisScoreToCycle[i]) + cycle.CalScore(get<2>(m_vDisScoreToCycle[i]), k - get<0>(m_vDisScoreToCycle[i]));
  }
  return *std::max_element(m_vRet.begin(),m_vRet.end());
}
void dfsLen(int cur, const long long llNeedNode)
{ 
  if (get<0>(m_vDisScoreToCycle[cur]) < llNeedNode)
  {
    return ;
  }
  long llScoer = 0;
  int r = cur;
  for(int i = 0 ; i < llNeedNode;i++ )
  {
    llScoer += r;
    r = m_receiver[r];
  }
  m_vRet[cur] = llScoer;
  while (get<0>(m_vDisScoreToCycle[m_receiver[cur]]) >= llNeedNode)
  {
    llScoer += r - cur;
    cur= m_receiver[cur];
    r = m_receiver[r];
    m_vRet[cur] = llScoer;
  }   
}
std::tuple<int,long long,int> dfs(int cur)
{
  auto& curRes = m_vDisScoreToCycle[cur];
  if (-1 != get<0>(curRes))
  {
    return curRes;
  }
  if (!m_setNotCycle.count(cur))
  {
    return curRes = std::make_tuple(0,0,cur);
  } 
  auto [iDis,iScore,iCycle] = dfs(m_receiver[cur]);
  return curRes = std::make_tuple(iDis+1,iScore+cur, iCycle);
}   
std::unordered_set<int> m_setNotCycle,m_setInDeg0;//非环上点； 入度为0的点
vector<tuple<int,long long,int>> m_vDisScoreToCycle;
std::unordered_map<int, int> m_mNodeToCycle;
vector<long long> m_vRet;
int  m_c;
vector<int> m_receiver;