[CERC2017]Cumulative Code

思路

好像是数论+记忆化搜索？
把子树分成有父亲（A）和无父亲（B）两种情况，这两种情况的删除顺序应该是不相同的。
首先，我们来讨论一下prufer编码（这个太长了，把他简称“P”好了）的总和。
我们把以编号xx为根，深度为kk的P的和记为fx(k)fx(k)。设fx(k)=akx+bk+ck(x div 2)fx(k)=akx+bk+ck(x div 2)，那么：

做到这里，我们发现：原来ak,bk,ckak,bk,ck都是可以递归的！
类似的，我们记录gx(k,i)gx(k,i)表示xx为根，kk层，已经删了ii个点的题目中要求的答案。
同样的，可以得到：

这里也可以递归来求。
但是，如果直接递归求解，时间复杂度会很高，大概是O(2k)O(2k)的。
所以，我们需要一些技巧：
如果没有询问落在一个区间内，那么这个区间不去递归，而是直接返回0；
否则，记忆化一些状态。
具体来说，就是记录：
1. 深度小于k div 2k div 2；
2. 这个区间落在[a,a+(m−1)d][a,a+(m−1)d]内。
记忆化的关键字在代码中讲，递归的方式也在代码中讲。
另外，答案采用多项式的方式保存，最终输出时计算一下多项式的值。

代码

#include <cstdio>
#include <algorithm>

const int maxm=15;

struct data//保存答案：ax+b+c(x div 2)
{
  long long a,b,c;

  data(long long a_=0,long long b_=0,long long c_=0)
  {
    a=a_;
    b=b_;
    c=c_;
  }
};

data res[maxm+1][1<<maxm];
int lm[maxm+1][1<<maxm],nowcase;
//lm记录最后一次记忆化是哪一次询问，res记录记忆化结果

inline int addleft(data& par,data son)
//par加上son的答案，其中son是par的左儿子
{
  par.a+=2*son.a+son.c;
  par.b+=son.b;
  return 0;
}

inline int addright(data& par,data son)
//par加上son的答案，其中son是par的右儿子
{
  par.a+=2*son.a+son.c;
  par.b+=son.a+son.b;
  return 0;
}

data search(int deep,int nextq,int m,int d,int hasparent)
/*
 *这里：
 *deep是这个点的深度
 *nextq代表这个区间的左端点
 *记忆化的key值是(deep,nextq)
 *m是最小能满足nextq+m*d大于(1<<deep)-1的m（大概吧）
 *d是题目中的
 *hasparent决定了是A情况还是B情况
 */
{
  if(deep==1)
    {
      data ans(0,0,1);
      return ans;
    }
  int size=(1<<deep)-1,mem=(deep<=maxm)&&(hasparent)&&(nextq+m*d>=size);
  if(mem&&(lm[deep][nextq]==nowcase))//如果在这次询问中被记忆化了，直接返回值
    {
      return res[deep][nextq];
    }
  data sol(0,0,0);//记录答案
  int nownext=nextq,sonsize=(1<<(deep-1))-1;
  if((nownext<sonsize)&&(m>0))//如果这个左子树有对答案产生贡献的点
    {
      int deltam=std::min(m,(sonsize-nownext-1)/d+1);//求m的变化量，也就是上面说的m值
      addleft(sol,search(deep-1,nownext,deltam,d,1));//将左边的答案加入这个的答案
      m-=deltam;
      nownext+=deltam*d;//防止nownext到达负数
    }
  nownext-=sonsize;
  if(!hasparent)//如果时B类型的子树，删完左边后需要删根，然后删右边
    {
      if((!nownext)&&(m>0))//如果这个点对答案产生贡献，则计算答案
        {
          nownext+=d;
          --m;
          sol.a+=2;
          ++sol.b;
        }
      --nownext;
    }
  if((nownext<sonsize)&&(m>0))//如果右子树有对答案产生贡献的点
    {
      int deltam=std::min(m,(sonsize-nownext-1)/d+1);//这一部分和左子树基本相同
      addright(sol,search(deep-1,nownext,deltam,d,hasparent));
      m-=deltam;
      nownext+=deltam*d;
    }
  nownext-=sonsize;
  if(hasparent)//A类型的子树，需要先计算完左右子树，再计算根
    {
      if(m>0)
      //如果可以对答案产生贡献，就增加答案
      //这里如果m>0，代表nextq一定为0了，否则m还可以继续减小至0，不符合“最小”的条件
        {
          ++sol.c;
        }
    }
  if(mem)//记忆化一下答案
    {
      lm[deep][nextq]=nowcase;
      res[deep][nextq]=sol;
    }
  return sol;
}

int n,q,a,m,d;

int main()
{
  scanf("%d%d",&n,&q);
  while(q--)
    {
      ++nowcase;
      scanf("%d%d%d",&a,&d,&m);
      data ans=search(n,a-1,m,d,0);//计算答案多项式，这里a-1是由于根节点的编号为1
      printf("%lld\n",ans.a+ans.b);//计算x为1时的答案多项式的值
    }
  return 0;
}