ABC036-D 塗り絵

const ll MOD=(ll)1e9+7;
const ll inf=(ll)1e14;
int n,m,h,w;
vector<int> v[100001];
ll f[100001],g[100001];
bool fpast[100001],gpast[100001];
ll Rank[100001];
int r=0;

void dfs(int now){
  Rank[now]=r;
  r++;
  for(int i=0;i<(int)v[now].size();i++){
    if(Rank[v[now][i]]!=inf)continue;
    dfs(v[now][i]);
  }
}

int memo(int now,int color){
  if(color==0){
    if(fpast[now])return f[now];
    else {
      f[now]=memo(now,1);
      ll temp=1;
      for(int i=0;i<(int)v[now].size();i++){
        if(Rank[v[now][i]]<Rank[now])continue;
        temp=((temp%MOD)*(memo(v[now][i],1)%MOD))%MOD;
      }
      f[now]=(temp+f[now])%MOD;
      fpast[now]=1;
      return f[now];
    }
  }else{
    if(gpast[now])return g[now];
    else{
      ll temp=1;
      for(int i=0;i<(int)v[now].size();i++){
        if(Rank[v[now][i]]<Rank[now])continue;
        temp=(temp%MOD*memo(v[now][i],0)%MOD)%MOD;
      }
      g[now]=temp;
      gpast[now]=1;
      return g[now];
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>n;
  for(int i=0;i<n-1;i++){
    int a,b;cin>>a>>b;
    a--;b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  for(int i=0;i<n;i++)Rank[i]=inf;
  dfs(0);
  print(memo(0,0));
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}

• メモ化再帰なのはわかったけど、漸化式思いつかなかったなー
• こういうのって蟻本のってたっけ？