树的解构

11.25 T2

棵以 1 为根的有 n 个结点的有根外向树。会进行n-1次操作，每次都会从未删掉的边中等概率选择一条边将其删去。记这条边为 a → b，则删去这条边的代价是删边时 b 的子树大小（包括 b 自己）；删去这条边后 b 为根的子树会形成一棵新的以 b 为根的有根树

对于每个点，怎样才会对它的某个祖先产生1的贡献？

只能切链接它的那一个祖先和那个祖先的儿子（也是这个点的祖先）的边，概率是1/(depth[x]-depth[y])因为它们之间有depth[x]-depth[y]条边，对于每个点对它所有的祖先求和，在对所有点的对它们各自所有的祖先再求和，时间复杂度O（n * n* logn),先维护一个前缀和,降到 （n* logn)，然后用线性求逆元O(n)

关于线性求逆元：inv[i]=(mod-mod/i)*inv[mod%i]%mod;

令t=mod/i,k=mod%i

则t*i+k恒等0（%mod）

t/k+1/i===0

inv[i]=(-(mod/i))*inv[mod%i]

inv[i]=(mod-(mod/i))*inv[mod%i]

到这就做完了

交一发 TLE

毒瘤数据用dfs爆栈

继续TLE

大力卡常，去STL

还是TLE

开fread

终于A了

#include<cstdio>
#include<iostream>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define LL long long
#define re register
#define mod 1000000007
#define N 2000010
using namespace std;
LL n,ans;
LL d[N],sum[N];
int head[N],nxt[N],ver[N];
int cnt;
inline void insert(int x,int y)
{
	nxt[++cnt]=head[x];
	ver[cnt]=y;
	head[x]=cnt;
}
LL i,x;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int res;
char ch;
inline int read() {
	res=0;
	ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
	return res;
}
int q[N];
int l,r;
inline void bfs()
{
	l=1,r=0;
	q[++r]=1;
	while(r-l+1)
	{
		x=q[l++];
		for (i=head[x];i;i=nxt[i])
		{
			d[ver[i]]=d[x]+1;
			q[++r]=ver[i];
		}
	}
}
int main()
{
	
//	freopen("deconstruct.in","r",stdin);freopen("deconstruct.out","w",stdout);
	n=read();
	for (i=2;i<=n;i++)	{insert(read(),i);}
	bfs();
	sum[0]=sum[1]=1;
	for (i=2;i<=n;i++)
	{
		sum[i]=(mod-mod/i)*sum[mod%i];
		if(sum[i]>=mod) sum[i]%=mod;
	}
	sum[0]=0;
	for (i=1;i<=n;i++)
	{
		sum[i]+=sum[i-1];
		if(sum[i]>=mod) sum[i]-=mod;
	}
	for (i=1;i<=n;i++)	ans+=sum[d[i]];
	printf("%lld",ans%mod);
	return 0;
}