[COCI 2023/2024 #3] Slučajna Cesta 题解

· · 题解

考虑如何 O(n) 求出结点 1 的答案，然后再使用换根。

现在 Vito 从结点 1 出发（即令根结点为 1）。显然同一条边不会被走过两次，因为如果这条边上是红蛇，那么前一个点的编号必然比后一个点小，走回去必然会被攻击，反之依然

对于一个结点 u，令 C_u 表示其儿子集合，同时设 k=|C_u|，如果从它开始往下走，有 \dfrac{1}{2^k} 的概率所有路都不能走，剩下的 \dfrac{2^k-1}{2^k} 的概率中往每个子结点走的概率相等，即 \dfrac{2^k-1}{k2^k}。于是令 f_u 表示从结点 u 往下走的路线美感度的期望（不包括自身的贡献，即 v_u），可以得出转移方程：

f_u=\sum\limits_{i\in C_u}\frac{2^k-1}{k2^k}(f_i+v_i)

前文提到对于每个结点，往所有出边走的概率相等，可以借助这一点进行换根。即对于每个结点按比例加入从父亲下传的贡献即可。具体实现可以参考代码。

时间复杂度 O(n\log P)，其中 P=10^9+7，那个 \log 是求逆元的。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=1e9+7;
int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)(r*=a)%=p;
    (a*=a)%=p,b>>=1;
  }
  return r;
}
int inv(int x){
  return qpow(x,p-2);
}
int sp(int x){
  return (1-qpow(inv(2),x)+p)*inv(x)%p;
} // 有 x 个儿子时走到单个儿子的概率
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin>>n;
  vector<vector<int> > g(n);
  for(int i=1;i<n;i++){
    int f; cin>>f;
    g[f-1].emplace_back(i);
  }
  vector<int> w(n),f1(n),f2(n),r(n);
  for(auto &i:w)cin>>i;
  function<void(int)> dfs1=[&](int u){
    int x=sp(g[u].size());
    for(int i:g[u])
      dfs1(i),(f1[u]+=(f1[i]+w[i])*x%p)%=p;
  }; // 处理出根结点答案
  function<void(int,int)> dfs2=[&](int u,int f){
    int x1=sp(g[u].size()),x2=sp(g[u].size()+1);
    if(u){
      int x3=sp(g[f].size());
      if(f)f2[u]=((f2[f]-f1[u]-w[u]+(p<<1))*x3%p+f1[f]+w[f])%p; // 父亲不是根
      else{
        int x4=sp(g[f].size()-1);
        f2[u]=((f1[f]-(f1[u]+w[u])*x3%p+p)*x4%p*inv(x3)%p+w[f])%p;
      } // 父亲是根
      r[u]=(f2[u]*x2%p+f1[u]*x2%p*inv(x1)%p+w[u])%p;
    }
    else r[u]=(f1[u]+w[u])%p; // 根结点
    for(int i:g[u])dfs2(i,u);
  };
  dfs1(0),dfs2(0,0);
  for(int i:r)cout<<i<<'\n';
  return 0;
}