読者です 読者をやめる 読者になる 読者になる

TreeDistance (TCO14 Round 3B d1 hard)

問題:N頂点の木Tが与えられます.「辺を一つ除いて,新たに付け加えて木にする」 という操作をK回以下出来るとき何種類の木が出来るでしょう?N,K≤50

まず, TからK回以下で木Xに出来る⇔TとXの両方に含まれる辺がN-1-K本以上(→は自明,左はいつかのこどふぉEに構成する問題が出た(
CF345 - sigma425のブログ).

Tの辺集合をEとして,Eのsubset Sに対して,SがTとXの両方に含まれる ようなものの個数を考えると,Sの連結成分の個数をC個,その大きさをn1,n2,..nCとすると,N^(C-2) * Πni になる.
これは非自明なんだけど,Prufer Sequenceと木との対応を知っていれば,そこからCayleyの式N^(N-2)が出てくることとの一般化として,これがわかる(sequenceに出てくる回数+1が次数で,連結成分ciとつなぐときはつなぎ方がni通りあるため,結局因数分解すると(n1+n2+...)^(C-2) * (+1回分の係数) となる.)

なので後は木DPで,dp[v][x][n]=v以下でx本を明確には固定せずに,今連結成分の大きさがn とやって,あとは包除.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
ll mod=1e9+7;
void add(ll &x,ll y){
	x+=y;
	x%=mod;
}
ll C[51][51];
vector<int> G[50];
int N;
int sz[50];
ll dp[50][51][51];
ll tmp[51][51][51];
void dfs(int v){
	sz[v]=1;
	for(int u:G[v]) dfs(u),sz[v]+=sz[u];
	rep(k,G[v].size()+1) rep(i,51) rep(j,51) tmp[k][i][j]=0;
	tmp[0][0][1]=1;
	int S=1;
	int K=G[v].size();
	rep(i,K){
		int u=G[v][i];
		rep(x,S) rep(n,S+1) if(tmp[i][x][n]){
			rep(ax,sz[u]+1) rep(an,sz[u]+1) add(tmp[i+1][x+ax][n+an],tmp[i][x][n]*dp[u][ax][an]);
		}
		S+=sz[u];
	}
	rep(x,S) rep1(n,S){
		dp[v][x][n]=tmp[K][x][n];
		add(dp[v][x+1][0],tmp[K][x][n]*n);
	}
//	rep(x,S+1) rep(n,S+1) printf("dp[%d][%d][%d]=%lld\n",v,x,n,dp[v][x][n]);
}
ll Co(int x,int y){
	if(x==y) return 1;
	return C[x][y];
}
ll ex(ll x,int p){
	if(p==-1){
		ll a=1;
		rep(i,x+1){
			if(a%N==0){
				a/=N;
				break;
			}
			a+=mod;
		}
		return a;
	}
	ll a=1;
	while(p){
		if(p%2) a=a*x%mod;
		x=x*x%mod;
		p/=2;
	}
	return a;
}
class TreeDistance{
	public:
	int countTrees(vector <int> p, int K){
		rep(i,51){
			C[i][0]=C[i][i]=1;
			for(int j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
		}
		N=p.size()+1;
		rep(i,N-1) G[p[i]].pb(i+1);
		dfs(0);
		K=max(0,N-1-K);
		ll ans=0;
		for(int i=K;i<=N-1;i++){
			ll ad=dp[0][N-i][0]*ex(N,N-i-2)%mod*Co(i-1,K-1)%mod;
			if((i-K)%2==1) ad=mod-ad;
			add(ans,ad);
		}
		return ans;
	}
};