【NOIP 模拟赛】Evensgn 剪树枝 树形dp

由于树规做的少所以即使我考试想出来正确的状态也不会转移。

一般dp的转移不那么繁杂（除了插头.....），即使多那也是清晰明了的，而且按照树规的一般思路，我们是从下到上的，所以我们要尽量简洁地从儿子那里的状态转移过来。

I.我们定义状态数组f[i][0/1]，f[i][0]表示在以这个点为根的子树里，除他以外的部分不含小黑点的方案数，f[i][1]表示以这个点为根的子树里包含其在内含黑点的方案数。

II.我们考虑初始化，对于一个点他的1状态是初始为无得所以为0，对于一个点他的0状态初始是有一个的所以为1

III.我们考虑转移，对于一个f[i][0]=(f[son0][1] or f[son0][0])*(f[son1][1] or f[son1][0])..............（or字面意思），对于一个f[i][1]，如果他为黑那么，f[i][1]=f[i][0]，如果他不为黑那么f[i][1]=sigma(i from son0 to sonn) {f[i][1]*pai(j from son0 to sonn(j!=i))(f[j][0] or f[j][1])}，注意如果一个点为黑那么他的f[i][0]是得不到转移的。

最后我们输出f[root][1]就是最终结果了。

#include <cstdio>
typedef long long LL;
namespace Pre{
  inline void read(int &sum){
    register char ch=getchar();
    for(sum=0;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';sum=(sum<<1)+(sum<<3)+ch-'0',ch=getchar());
  }
  const LL P=1000000007;
  const int N=100010;
  LL f[N][2];
  int a[N],n;
}
namespace Tree{
  struct tree{
    int to,next;
  }c[Pre::N<<1];
  int head[Pre::N],t;
  inline void add(int x,int y){
    c[++t].to=y;
    c[t].next=head[x];
    head[x]=t;
  }
  void dfs(int x,int fa){
    using namespace Pre;
    f[x][1]=0,f[x][0]=1;
    for(int i=head[x];i;i=c[i].next)
      if(c[i].to!=fa){
        dfs(c[i].to,x);
        f[x][1]=(f[x][0]*f[c[i].to][1]%P+f[x][1]*f[c[i].to][0]%P)%P;
        f[x][0]=f[x][0]*f[c[i].to][0]%P;
      }
    if(a[x]) f[x][1]=f[x][0];
    else f[x][0]=f[x][1]+f[x][0];
  }
}
inline void Init(){
  using namespace Pre;
  using Tree::add;
  read(n);
  for(int i=1,x;i<n;i++)
    read(x),add(x+1,i+1),add(i+1,x+1);
  for(int i=1;i<=n;i++)
    read(a[i]);
}
inline void Work(){
  Tree::dfs(1,0);
  printf("%lld",Pre::f[1][1]);
}
int main(){
  Init();
  Work();
}