Lijinrui299792458

不做沉底的木做举重若轻的船。

树上移动

发表于

题目描述

$n\le 10^5$。

思路

首先，考虑每一个点的贡献：每一个点被选择后，如果不终止，一定随机选择下一个点，计算这之间的期望路径长度（树形 DP）。这样，我们只需计算每个点期望被选择的次数。此时该问题只与节点的值有关。

当已有 $i$ 个点为 $1$ 时，选择值为 $0/1$ 的点的期望次数为：
$$
f_{i,0}=\frac{1}{n}+\frac{f_{i+1,1}}{n}+\frac{i\cdot f_{i-1,0}}{n}+\frac{(n-i-1)f_{i+1,0}}{n}
$$

$$
f_{i,1}=\frac{1}{n}+\frac{f_{i-1,0}}{n}+\frac{(i-1)f_{i-1,1}}{n}+\frac{(n-i)f_{i+1,1}}{n}
$$

整理可得，
$$
(n-i-1)f_{i+1,0}+f_{i+1,1}=n\cdot f_{i,0}-1-i\cdot f_{i-1,0}
$$

$$
f_{i+1,1}=\frac{n\cdot f_{i,1}-1-f_{i-1,0}-(i-1)f_{i-1,1}}{n-i}
$$

我们用 $f_{1,0/1}$ 来表示每一个 $f$，用 $f_{n-1,0/1}$ 的转移列出方程。

边界：
$$
f_{0,0/1}=f_{n,0/1}=0
$$
另外，$f_{1,1}$ 和 $f_{n-1,0}$ 的转移没有 $\frac{1}{n}$ 这一项，因为此时选择的这个点是没有贡献的（选择了就结束了，而贡献是选择后转移走的次数）。

详见代码。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll ny[100001];
const ll mod=1e9+7;

struct F
{
	ll a,b,c;
	inline ll val(ll x,ll y){return (a*x+b*y+c)%mod;}
}f[100001][2];
F operator + (F f1,F f2)
{
	f1.a=(f1.a+f2.a)%mod,f1.b=(f1.b+f2.b)%mod,f1.c=(f1.c+f2.c)%mod;
	return f1;
}
F operator - (F f1,F f2)
{
	f1.a=f1.a-f2.a,f1.b=f1.b-f2.b,f1.c=f1.c-f2.c;
	f1.a=(f1.a+mod)%mod;f1.b=(f1.b+mod)%mod;f1.c=(f1.c+mod)%mod;
	return f1;
}
F operator + (F _,ll x)
{
	_.c=(_.c+x)%mod;
	return _;
}
F operator - (F _,ll x)
{
	_.c=((_.c-x)%mod+mod)%mod;
	return _;
}
F operator * (ll x,F _)
{
	_.a=_.a*x%mod,_.b=_.b*x%mod,_.c=_.c*x%mod;
	return _;
}
F operator / (F _,ll x)
{
	x=ny[x],_.a=_.a*x%mod,_.b=_.b*x%mod,_.c=_.c*x%mod;
	return _;
}//以 f[1][0],f[1][1] 表示 f=a*f[1][0]+b*f[1][1]+c

ll qkp(ll x,ll y)
{
	ll ret=1LL,_=x;
	while(y)
	{
		if(y&1)ret=ret*_%mod;
		y>>=1;
		_=_*_%mod;
	}
	return ret;
}

char mp[100000];ll dis[100001],n,fa[100001];
vector <ll> son[100001];
ll sz[100001];

void dfs(ll x)
{
	sz[x]=1;
	for(ll i:son[x])
	{
		dfs(i);
		sz[x]+=sz[i];
		dis[x]+=dis[i]+sz[i];
	}
}
void dfs2(ll x)
{
	for(ll i:son[x])
	{
	dis[i]+=dis[x]-dis[i]+n-(sz[i]<<1);
		dfs2(i);
	}
}
bool ntpr[100001];ll pr[100001],tnc=0;
int main()
{
	freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    scanf("%lld",&n);
	scanf("%s",mp);
	ll cnt=0;
	for(int i=0;i<n;i++)cnt+=(mp[i]=='1');
	for(ll i=2;i<=n;i++)scanf("%lld",&fa[i]),son[fa[i]].push_back(i);
	dfs(1LL);
	dfs2(1LL);
	ny[1]=1;
	for(ll i=2;i<=n;i++)
	{
		if(!ntpr[i])pr[++tnc]=i,ny[i]=qkp(i,mod-2);
		for(int j=1;j<=tnc&&pr[j]*i<=n;j++)
		{
			ny[pr[j]*i]=ny[i]*ny[pr[j]]%mod;
			ntpr[pr[j]*i]=1;
			if(!i%pr[j])break;
		}
	}//类比欧拉筛求逆元，其实暴力也可以过
	for(int i=1;i<=n;i++)dis[i]=dis[i]%mod*ny[n]%mod;//树形 DP
	f[1][0].a=1LL,f[1][1].b=1LL;//初始值
	for(ll i=2;i<n;i++)
	{
		f[i][1]=(n*f[i-1][1]-(ll)(i>2LL)-f[i-2][0]-(i-2)*f[i-2][1])/(n-i+1);
		f[i][0]=n*f[i-1][0]-1LL-(i-1)*f[i-2][0];
		f[i][0]=(f[i][0]-f[i][1])/(n-i);
	}//递推
	ll s1,s2,s3,s4,s5,s6;
	s1=(f[n-1][0]-(n-1)*f[n-2][0]/n).a;
	s2=(f[n-1][0]-(n-1)*f[n-2][0]/n).b;
	s3=(f[n-1][0]-(n-1)*f[n-2][0]/n).c;
	s4=(f[n-1][1]-(n-2)*f[n-2][1]/n-f[n-2][0]/n-ny[n]).a;
	s5=(f[n-1][1]-(n-2)*f[n-2][1]/n-f[n-2][0]/n-ny[n]).b;
	s6=(f[n-1][1]-(n-2)*f[n-2][1]/n-f[n-2][0]/n-ny[n]).c;
	ll x,y;
	s2*=s4,s2-=s1*s5,s2%=mod,s2+=mod,s2%=mod,s3*=s4,s3-=s1*s6,s3%=mod,s3+=mod,s3%=mod;
	y=s3*qkp(s2,mod-2)%mod,y=(mod-y)%mod;
	s6=mod-(s6+s5*y)%mod;
	s6%=mod;
	x=s6*qkp(s4,mod-2)%mod;//直接暴力解二元方程组
	ll a[2];
	a[0]=f[cnt][0].val(x,y),a[1]=f[cnt][1].val(x,y);
	a[0]+=ny[n],a[0]%=mod,a[1]+=ny[n],a[1]%=mod;
	ll ans=0;
	for(int i=0;i<n;i++)
	{
		if(mp[i]=='1')ans=(ans+a[1]*dis[i+1])%mod;
		else ans=(ans+a[0]*dis[i+1])%mod;
	}//统计答案
	printf("%lld",ans);
	return 0;
}

Summary

由于选点是随机的，因此树上路径长与点的翻转其实是独立的。因此我们把问题分成两部分来解决。