#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n;
ll a[1000010],vis[1000010],f[1000010],p2[1000010];
ll qpow(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
	return ans;
}
vector<int> e[1000100];
ll dp[1000010],dp2[1000010],sum[1000010],ans[1000010];
ll g(ll x){
	return qpow(x,mod-2)%mod*(1-qpow(p2[x],mod-2)+mod)%mod;
}
void dfs(int x,int xfa){
	for(int y:e[x])if(y!=xfa){
		dfs(y,x);
		sum[x]=(sum[x]+dp[y])%mod;
	}
	dp[x]=(a[x]+g(e[x].size()-(x!=1))*sum[x]%mod)%mod;
}
void dfs2(int x,int xfa){
	ll sx=sum[x];
	sx=(sx+dp2[x])%mod;
	for(int y:e[x])if(y!=xfa){
		ll s=(sx-dp[y]+mod)%mod;
		dp2[y]=(a[x]+g(e[x].size()-1)*s%mod)%mod;
		ans[y]=(a[y]+g(e[y].size())*(sum[y]+dp2[y])%mod)%mod;
		dfs2(y,x);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	f[0]=1;
	p2[0]=1;
	for(int i=1;i<=n;i++){
		f[i]=f[i-1]*i%mod;
		p2[i]=p2[i-1]*2%mod;
	}
	for(int i=2,x;i<=n;i++){
		cin>>x;
		e[x].push_back(i);
		e[i].push_back(x);
	}
	for(int i=1;i<=n;i++){
		cin>>a[i]; 
	}
	dfs(1,0);
	ans[1]=dp[1];
	dfs2(1,0);
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

这题可以自己做，很水的换根DP（当然我的思路和题解有一点点差别）

关键思路在于每个点要么不走，要么等概率走到他的相邻节点，以及你不会来回走。

所以 dp[i][0] 为 i 无法到达父亲节点时的期望（也就是预处理）

sum1[x] 为 x 的父亲节点无法到达 x 时 x 的父亲节点的期望值。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10,P=1e9+7;
int qpow(int a,int b){int ans=1;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;}
vector<int>G[N];
int dp[N][2],sum[N],sum1[N],a[N];
void dfs1(int x,int f)
{
	sum[x]=0;int siz=0;
	for(int y:G[x])if(y!=f)
	{
		dfs1(y,x);siz++;
		sum[x]=(sum[x]+dp[y][0])%P;
	}
	dp[x][0]=(a[x]+(sum[x]*qpow(siz,P-2))%P*((1-qpow(qpow(2,siz),P-2))%P+P)%P)%P;
}
void dfs2(int x,int f)
{
	int siz=G[x].size();
	for(int y:G[x])if(y!=f)
	{
		int siz1=G[y].size();
		int t=((sum[x]-dp[y][0]+sum1[x])%P+P)%P;
		sum1[y]=(a[x]+(t*qpow(siz-1,P-2))%P*((1-qpow(qpow(2,siz-1),P-2))%P+P)%P)%P;
		dp[y][1]=(a[y]+((sum[y]+sum1[y])*qpow(siz1,P-2))%P*((1-qpow(qpow(2,siz1),P-2))%P+P)%P)%P;
		dfs2(y,x);
	}
}
signed main()
{
	int n;cin>>n;
	for(int i=2;i<=n;i++)
	{
		int x;cin>>x;
		G[i].push_back(x);
		G[x].push_back(i);
	}
	for(int i=1;i<=n;i++)cin>>a[i];
	dfs1(1,0);
	dp[1][1]=dp[1][0];
	dfs2(1,0);
	for(int i=1;i<=n;i++)cout<<dp[i][1]<<'\n';
	return 0;
}

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