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; } };