自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:55:56，当前版本为作者最后更新于2024-03-13 15:19:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

考虑如何 $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;
}