DTOJ#5202. Deconstruction of tree

Portal

Mivik likes Eprom's deconstruction club, so he wants to deconstruct a tree.

Mivik found a tree 1 1 1 is the root of n n A rooted extrovert tree with n nodes. Mivik will ( n − 1 ) (n − 1) (n − 1) operations, each time Mivik will select an edge from the undeleted edge with medium probability to delete it. Remember this side as a → b a → b a → b, then the cost of deleting this edge is when deleting the edge b b Subtree size of b (including b b b) themselves; After deleting this edge b b A subtree with b as its root will form a new one b b b is a rooted tree.

For example, the following figure shows the rooted tree found by Mivik:

If Mivik chooses 1 → 2 1 \to 2 1 → 2 and delete it, then the price is 3 3 3( 2 2 2 is shared in the subtree 2 , 4 , 5 2,4,5 2, 4 and 5), and then this will happen:

If Mivik deletes it at this time 2 → 4 2 \to 4 2 → 4 this side, then the price is 1 1 1( 4 4 In the subtree where 4 is located, there are only 4 4 4 (one node),
Then this happens:

Mivik wants to know that he did this ( n − 1 ) (n − 1) What is the total expected cost of (n − 1) operations. Because Mivik doesn't like too large numbers, you just need to output the expected value pairs 1 0 9 + 7 10^9 + 7 Results of 109 + 7 mold taking.

There are two lines to enter.

The first line is a positive integer n n n. Represents the size of the given rooted tree.

The second line gives ( n − 1 ) (n − 1) (n − 1) positive integer, th i i i number a i a_i ai indicates ( i + 1 ) (i + 1) The father of node (i+1) on the rooted tree is a i a_i ai​.

Output a non negative integer per line, indicating the expected pair of costs 1 0 9 + 7 10^9 + 7 Results of 109 + 7 mold taking.

Sample input 1

4
1 2 2

Sample output 1

4

Example 1 explanation

The total cost of deconstruction is 1 / 3 1/3 The probability of 1 / 3 is 3 3 3. Yes 1 / 3 1/3 The probability of 1 / 3 is 4 4 4. Yes 1 / 3 1/3 The probability of 1 / 3 is 5 5 5, so the price expectation is 4 4 4.

Sample input 2

5
1 1 2 2

Sample output 2

5

Example 3

See deconstruct / deconstruct3 under the contestant directory In and deconstruct / deconstruct3 ans.

For all test points, meet 1 ≤ n ≤ 2 × 1 0 6 1 \leq n \leq 2 \times 10^6 1≤n≤2 × 106. Ensure that the given rooted tree is legal.
The specific limitations of each subtask are shown in the following table:

Subtask number Score Special restrictions
1 1 1 10 10 10 a i = 1 a_i=1 ai​=1
2 2 2 15 15 15 a i = i a_i=i ai​=i
3 3 3 25 25 25 n ≤ 500 n \leq 500 n≤500
4 4 4 50 50 50 nothing

Chengdu No.7 Middle School noip 2020 simulation

Consider calculating the answer for each point.
It is said that some gods stare at the law i i i's answer is ∑ j d e p [ i ] 1 j \sum_j^{dep[i]} \frac{1}{j} Σ jdep[i] j1, sum directly.
u p d a t e : update: update: it is said to be for root to i i I, considering the contribution probability of each edge, i.e ( l e n − 1 ) ! l e n ! \frac{(len-1)!}{len!} len!(len−1)! , summation is the above formula.
Konjaku Science D P DP I'm stupid. So we consider pretreatment f [ i ] f[i] f[i] indicates the length is i i The answer at the end of the chain of i.
Transfer is enumeration i i Location of i f [ i ] = ( ∑ f [ j − 1 ] × C i − 1 j − 1 × A i − j ) + A i f[i]=(\sum f[j-1]\times C_{i-1}^{j-1}\times A_{i-j})+A_{i} f[i]=(∑f[j−1]×Ci−1j−1​×Ai−j​)+Ai​
Expand simplification, prefix and optimization O ( n ) O(n) O(n) treatment.

#include<bits/stdc++.h>
#define N 2000006
using namespace std;
inline char GET_CHAR ( void )
{
    static char buf[1<<23],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2) ? EOF : *p1++;
}
inline int read ( void )
{
	int x=0;char ch;
	while ( !isdigit(ch=GET_CHAR()) ) ;
	for ( x=ch^48;isdigit(ch=GET_CHAR()); ) x=(x<<1)+(x<<3)+(ch^48);
	return x;
}
const int mod=1e9+7;
int jc[N],jcinv[N],f[N];
inline int power(int x,int c){
	int now=1;
	while(c){
		if(c&1)now=1ll*now*x%mod;
		x=1ll*x*x%mod;c>>=1;
	}
	return now;
}
inline void init(int n){
	jc[0]=1;
	for(int i=1;i<=n;++i)jc[i]=1ll*jc[i-1]*i%mod;
	jcinv[n]=power(jc[n],mod-2);
	for(int i=n-1;i+1;--i)jcinv[i]=1ll*jcinv[i+1]*(i+1)%mod;
	int sum=0;
	for(int i=1;i<=n;++i){
		f[i]=sum%mod;
		f[i]=(1ll*f[i]*jc[i-1]%mod+jc[i])%mod;
		sum=(sum+1ll*f[i]*jcinv[i]%mod)%mod;
	}
}
inline int C(int x,int y){
	if(x<y||y<0)return 0;
	return 1ll*jc[x]*jcinv[y]%mod*jcinv[x-y]%mod;
}
int ans=0,dep[N],n;
int tot,head[N],ver[N<<1],nex[N<<1];
inline void add(int x,int y){
	nex[++tot]=head[x];head[x]=tot;ver[tot]=y;
}
void dfs(int x,int las){
	ans=(ans+1ll*f[dep[x]]*C(n-1,dep[x])%mod*jc[n-1-dep[x]]%mod)%mod;
	for(int i=head[x];i;i=nex[i]){
		int y=ver[i];
		if(y==las)continue;
		dep[y]=dep[x]+1;
		dfs(y,x);
	}
}
int main(){
//	freopen("deconstruct.in","r",stdin);
//	freopen("deconstruct.out","w",stdout);
    n=read();
    init(n+1);
    for(int i=2;i<=n;++i){
    	int x=read();
    	add(x,i);add(i,x);
    }
    dfs(1,0);
	ans=1ll*ans*jcinv[n-1]%mod;
    printf("%d\n",(ans+mod)%mod);
    return 0;
}

Posted by Skittalz on Wed, 04 May 2022 01:28:57 +0300