论如何 AK WFYZ公益班测试-20240330

__vector__ · 2024-03-30 15:39:56 · 题解

晚了半个点参赛，因为此前 vp 了上一场 CF Div.4（AK）

C 没测第二个样例，刚好题目翻译有问题（事实不应该去重，但翻译成了去重），怒挂 50。
D 题我看最后一个点 n=2000，就以为 n \le 2000，事实上 n \le 2\cdot 10^5，挂 40。 F 题写的正解，然而要求的值看错了，导致没调出来，哎。

A - CF598A

套公式直接算。

B - CF598B

同一个长度为 len 的区间执行 k 次和执行 k \mod len 次效果是一样的，可以以此在每次操作中快速计算出每个字符新的位置。
注意到操作次数很少，模拟就可以。

C - CF598D

bfs 就行了，注意本题洛谷翻译是错的，应该按照题目警示贴来。

D - P2846

线段树维护，每个节点记录本区间答案，以及一个 lazytag 代表本区间灯状态是否反转。

E - CF461B

设状态 dp_{u,1/0}，代表 u 为根的子树，u 所在的连通块有一个/没有黑色节点，且其他连通块合法的方案数。

• 先考虑 x_u 为 1 的情况，此时对于每个子节点，如果其所在连通块有一个黑色节点，则不能保留其和 u 的连边，如果没有黑色节点，则其必须和 u 连边；简单地说，如果和 u 连边，那么自己连通块必须有一个黑色节点，反之必须没有。
  此时显然 dp_{u,0} = 0,dp_{u,1} =\prod\limits_{v \in son_u} (dp_{v,0}+dp_{v,1})
• 如果 x_u 为 0 呢？
  考虑 u 连通块中存在一个黑色节点的情况，此时必须有恰好一个连通块中存在一个 1 的子节点和自己连边，其余连通块存在一个黑色节点的子节点都必须和 u 断边，另外所有连通块不存在黑色节点的子节点都必须和 u 连边，得出结论： dp_{u,1}=\sum\limits_{s_1 \in son_u} (dp_{s_1,1}\cdot \prod\limits_{s_2 \neq s_1}(dp_{s_1,0}+dp_{s_2,0}))

  接下来考虑 u 连通块中没有黑色节点的情况，此时子结点中，如果一个子节点连通块中没有黑色，那么必须保留和 u 的边，否则必须删除和 u 的边，显然有结论：

  dp_{u,0} =\prod\limits_{v \in son_u} (dp_{v,0}+dp_{v,1})

  #include <bits/stdc++.h>
  using namespace std;
  #define FOR(i,a,b) for(int i=a;i<=b;i++)
  #define REP(i,a,b) for(itn i=a;i>=b;i--)
  typedef long long ll;
  const ll mod=1e9+7;
  int t;
  const int maxn=1e5+5;
  int n;
  int p[maxn];
  int x[maxn];
  vector<int> g[maxn];
  ll dp[maxn][2];
  ll qpow(ll a,ll b){
  ll ret=1;
  while(b){
      if(b&1)ret=ret*a%mod;
      a=a*a%mod;
      b>>=1; 
  }
  return ret;
  }
  ll inv(ll a){
  return qpow(a,mod-2);
  }
  void dfs(int u,int _fa){
  ll sum=1;
  for(int v:g[u]){
      if(v!=_fa){
          dfs(v,u);
          sum*=(dp[v][0]+dp[v][1]);
          sum%=mod;
      }
  }
  if(x[u]==1){
      dp[u][1]=sum;
  }else{
      for(int v:g[u]){
          if(v!=_fa){
              dp[u][1]+=dp[v][1]*(sum*inv(dp[v][0]+dp[v][1])%mod)%mod;
              dp[u][1]%=mod;
          }
      }
      dp[u][0]=sum;
  }
  }
  void solve(){
  scanf("%d",&n);
  FOR(i,0,n-2){
      int pi;
      scanf("%d",&pi);
      g[pi].emplace_back(i+1);
      g[i+1].emplace_back(pi);
  //  printf("%d --> %d\n",pi,i+1);
  } 
  FOR(i,0,n-1){
      scanf("%d",&x[i]);
  }
  dfs(0,-1);
  printf("%lld\n",(dp[0][1]%mod+mod)%mod);
  }
  int main(){
  t=1;
  while(t--){
      solve();
  }
  return 0;
  }

F - CF598E