TCO2014R3BH TreeDistance
問題概要(原文)
$N$ 頂点の木が与えられる．$K$ 回まで，「辺を $1$ つ選んで削除したのち，新しい辺を(木になるように)追加する」という操作が可能である．
最終的に得られる木は何通りか？
考察
まず簡単な問題を考える．
$T_{1},T_{2},\ldots, T_{k}$ なる $k$ 個の木に $k-1$ 本の辺を追加して，$1$ つの木にしたい．得られる木は何通りあるか？
結論からいうと，$|T|$ を木 $T$ を構成する頂点の数，$N = \sum{|T_i|}$ として，$\prod{|T_i|} N^{k-2}$ である．
これはケイリーの式の「$N$ 頂点のラベル付きの頂点，辺の木の数え方」から示せる． 具体的には $k$ 個の根付き森に，$1,\ldots,k-1$ 番の有向辺を追加して，$1$ つの根付き有向木にすることを考える． $i$ 番の辺を追加するときには，$N$ 個の頂点のどれかを始点に，自分が属する木以外の $k-i$ 個の木の根のどれかを選ぶ．
このようにして得られる木は各木の根の選び方が $\prod{|T_i|}$, 始点の選び方が $N^{k-1}$，終点の選び方が $(k-1)!$ 通りある．辺のラベルの付け方を考慮しないので，$(k-1)!$ で割ってやり，根の選び方も考慮しないので $N$ で割ってやる．すると，作ることが可能な木は $\prod{|T_i|}N^{k-2}$ 通りである． ここで重要なことは，森の個数と，木のサイズの積さえ分かればありうる木の個数が数えられることである．
気分として，グラフから $K$ 本辺を取り除いて，それぞれの連結成分のサイズの積と $N^{K-1}$ をかけたい気持ちになる． ここで，頂点 $0$ を根とする部分木から $k$ 本辺を取り除いて得られるグラフそれぞれについて，連結成分のサイズの積を足したものを考える．これらは互いに区別する必要がないのでまとめて計算できる． よって，$\mathrm{dp}(i,j,k)$ を頂点 $i$ を根とする部分木から $k$ 本辺を取り除いて，現在のサイズが $j$ であるときの「その他の連結成分のサイズの積」を足し上げたもの，とする．
しかし，このままでは元の辺をそのままつなぎ直してしまうケースがいくつも含まれているので，それを包除原理の要領で取り除いてやる必要がある．
元のグラフから $i$ 本ちょうど取り除いたときだけ作れる木の数を $A_{i}$ ，$B_{i} = \sum{j \mathrm{dp}(0,j,i)} N^{i-1}$ とすると，$A$ は以下の漸化式で定まる．
\[ A_{i} = B_{i} - \sum{ \binom{n-1-j}{i-j}A_{j}} \]
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class TreeDistance
{
public int countTrees(int[] p, int k)
{
const long MOD=(long)1e9+7;
var n=p.Length+1;
var G=new List<int>[n];
for(int i=0;i<n;i++)G[i]=new List<int>();
for(int i=0;i<n-1;i++)
G[p[i]].Add(i+1);
Func<int,KeyValuePair<int,long[,]>>dfs=null;
dfs=v=>
{
var sz=1;
var ret=new long[2,n+1];
ret[1,0]=1;
foreach(var t in G[v])
{
var res = dfs(t);
var nsz=sz+res.Key;
var dp=res.Value;
var next = new long[nsz+1,n+1];
for(int i=0;i<=sz;i++)
for(int j=0;j<sz;j++)
for(int ii=0;ii<=res.Key;ii++)
for(int jj=0;jj<res.Key;jj++)
{
if(ret[i,j]==0)continue;
if(dp[ii,jj]==0)continue;
next[i,j+jj+1]+=ret[i,j]*ii*dp[ii,jj];
next[i,j+jj+1]%=MOD;
next[i+ii,j+jj]+=ret[i,j]*dp[ii,jj];
next[i+ii,j+jj]%=MOD;
}
ret=next;
sz=nsz;
}
return new KeyValuePair<int,long[,]>(sz,ret);
};
var D=dfs(0).Value;
var E=new long[n];
for(int i=0;i<=n;i++)
for(int j=0;j<n;j++)
E[j]=(E[j]+i*D[i,j])%MOD;
long ans=0;
var binomial = new long[55,55];
binomial[0,0]=1;
for(int i=0;i<50;i++)
for(int j=0;j<50;j++)
{
binomial[i+1,j]+=binomial[i,j];
binomial[i+1,j+1]+=binomial[i,j];
binomial[i+1,j]%=MOD;
binomial[i+1,j+1]%=MOD;
}
for(int i=0;i<n;i++)
{
if(i>k)break;
E[i] =(long) (E[i]*BigInteger.ModPow(n,MOD-1+i-1,MOD)%MOD);
for(int j=0;j<i;j++)E[i]-=E[j]*binomial[n-1-j,i-j];
E[i]%=MOD;
E[i]=(E[i]+MOD)%MOD;
ans+=E[i];
}
ans%=MOD;
return (int)ans;
}
}
// Powered by Greed 2.0-RC
コメント
- むずいけど自力で解けた
