列表

详情

NC17241. B、Expected Number of Nodes

描述

Eddy likes to play with tree. Of course, it's not those green and natural trees, but those trees containing N vertices and N-1 edges and miraculously remaining connected. However, it's difficult for Eddy to remember every tree he likes. Some tree may be too large while some tree may have strange structure which is hard to be encoded in memory(in Eddy's brain). Thus, Eddy comes up with following way to contract a tree:

1. Select a subset of vertices.
2. While there's an unselected vertex with degree 1, delete it.
3. While there's an unselected vertex with degree 2, delete it and connect its neighbors.
4. Output the remaining tree.

However, choosing which subset in step 1 is a hard choice for Eddy. He decides to choose some subset of vertices containing exactly k vertices. From all possible choices, He will uniformly randomly choose one of them.

Now, you are wondering what would be the expected number of vertices after contracting. But, you don't know Eddy chooses which k in the first step. Then, you wants to find out all the answer for each k from 1 to N(total number of vertices).

输入描述

First line of input contains a positive integer N indicating the number of vertices of the tree.
For each following N-1 lines, each contains two space-separated positive integer ui, vi indicating that there's an edge between ui and vi.

1≤ N ≤ 5000
1 ≤ ui < vi ≤ N
It's guaranteed that the given input is a tree.

输出描述

Please output N lines. For i-th line, output one integer Z indicating the expected number of vertices module 1000000007(109+7) after contracting when k=i. One can show that the expected number of vertices can be represented as , then Z will be P x Q-1 module 1000000007(109+7)

示例1

输入: 

1

输出: 

1

示例2

输入: 

4
1 2
2 3
3 4

输出: 

1
2
3
4

示例3

输入: 

4
1 2
1 3
1 4

输出: 

1
2
250000005
4

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 265ms, 内存消耗: 118492K, 提交时间: 2018-07-27 16:07:04 

#include<iostream>
#include<cstdio>
#include<vector>
const int N=5e3+5;
typedef long long ll;
const int mod=1e9+7;
int n,size[N];ll C[N][N]={},ans[N],cnt[N],tot;
ll qpow(ll x,ll y) {
    ll res=1;
    for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;
    return res;
}
void pr() {
    C[0][0]=1;
    for(int i=1;i<=n;i++) {
        C[i][i]=C[i][0]=1;
        for(int j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
}
std::vector<int> g[N],w[N];
void dfs(int u,int fa) {
    size[u]=1;
    for(int v:g[u]) if(v!=fa) {
        dfs(v,u);
        size[u]+=size[v];w[u].push_back(size[v]);
    }
    if(size[u]!=n) w[u].push_back(n-size[u]);
    if(w[u].size()<=2) return;++tot;
    for(int v:w[u]) cnt[v]+=w[u].size()-2;
    for(int i=0;i<w[u].size();i++) for(int j=i+1;j<w[u].size();j++) cnt[w[u][i]+w[u][j]]--;
}
int main() {
    scanf("%d",&n);int u,v;
    for(int i=1;i<n;i++) scanf("%d%d",&u,&v),g[u].push_back(v),g[v].push_back(u);
    pr();dfs(1,1);for(int i=1;i<=n;i++) cnt[i]=(cnt[i]+mod)%mod;
    for(int i=1;i<=n;i++) {
        ans[i]=(tot*C[n][i]%mod+(n-tot)*(C[n][i]-C[n-1][i]+mod))%mod;
        for(int j=i;j<=n;j++) if(cnt[j]) ans[i]=(ans[i]+cnt[j]*C[j][i]%mod)%mod;
        ans[i]=ans[i]*qpow(C[n][i],mod-2)%mod;
        printf("%lld\n",ans[i]);
    }
    return 0;

}

C++11(clang++ 3.9) 解法, 执行用时: 247ms, 内存消耗: 68096K, 提交时间: 2018-07-26 21:09:17 

#include<bits/stdc++.h>
using namespace std;

#define FOR(a,b,c) for(int a=(b),a##_end__=(c);a<a##_end__;++a)
#define DOR(a,b,c) for(int a=(b)-1,a##_end__=(c);a>=a##_end__;--a)
#define Mod 1000000007
template<class T>inline bool chkmin(T&a,T const&b){return a>b?a=b,true:false;}
template<class T>inline bool chkmax(T&a,T const&b){return a<b?a=b,true:false;}
const int M=5005;
vector<int>E[M];
int Sz[M],cnt[M],C[M][M],S[M];
int n;
long long Pow(long long x,int k){
	long long res=1;
	for(;k;k>>=1,(x*=x)%=Mod)
		if(k&1) (res*=x)%=Mod;
	return res;
}
void dfs(int u,int fa){
	int m=0;
	Sz[u]=1;
	for(int v:E[u]) if(v!=fa) dfs(v,u);
	for(int v:E[u]) if(v!=fa){
		Sz[u]+=Sz[v];
		S[m++]=Sz[v];
	}
	if(~fa) S[m++]=n-Sz[u];
	FOR(i,0,m) cnt[S[i]]+=m-2;
	FOR(i,0,m) FOR(j,0,i) --cnt[S[i]+S[j]];
}
int main(){
	FOR(i,0,M) FOR(j,C[i][0]=1,i+1) C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
	scanf("%d",&n);
	FOR(i,1,n){
		int u,v;
		scanf("%d %d",&u,&v);
		E[u].push_back(v);
		E[v].push_back(u);
	}
	dfs(1,-1);
	FOR(k,1,n+1){
		long long ans=1LL*C[n][k]*n%Mod;;
		FOR(i,k,n) (ans+=1LL*C[i][k]*cnt[i])%=Mod;
		printf("%lld\n",(ans*Pow(C[n][k],Mod-2)%Mod+Mod)%Mod);
	}
	return 0;
}

上一题

© 2024 nowcoder.com