AtCoder ARC #165 : E - Random Isolation

この問題あんまり記憶にないな…。
https://atcoder.jp/contests/arc165/tasks/arc165_e

問題

N頂点の木と、正整数Kが与えられる。
K+1以上のサイズの連結成分がある限り、その連結成分の頂点を等確率で1つ選び、その頂点及びその頂点を端点とする辺を削除することを繰り返す。
操作回数の期待値を求めよ。

解法

1～NのPermutation Pに対し、その順で順次「点P[i]が属する連結成分がK+1以上のサイズなら、P[i]を消す」という風に読み替える。
各頂点vに対し、頂点vより先に他の頂点が消される結果、頂点vを消す順番が来たときに、サイズがK以下かどうか、を判定したい。
そこでvを根としてDFSを行い、SubTree内での消した頂点数と親方向と連結する残った頂点数に対し、その状態に至る組み合わせを数え上げて行こう。

int N,K;
vector<int> E[101];
const ll mo=998244353;

const int NUM_=2000003;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];


unordered_map<int,ll> dp[101];
ll ret;
void dfs(int cur,int pre) {
	unordered_map<int,ll> F;
	F[1]=1;
	
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		unordered_map<int,ll> T;
		FORR2(a,b,F) {
			FORR2(a2,b2,dp[e]) {
				(T[a+a2]+=b*b2)%=mo;
			}
		}
		swap(F,T);
	}
	
	if(cur!=pre) {
		F[1000]=1;
		dp[cur]=F;
	}
	else {
		FORR2(a,b,F) {
			int aa=a/1000;
			int ab=a%1000;
			
			if(ab>K) {
				 (ret+=factr[aa+ab]*fact[ab-1]%mo*fact[aa]%mo*b)%=mo;
			}
		}
	}
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>N>>K;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) {
		dfs(i,i);
	}
	cout<<ret%mo<<endl;
}

まとめ

落ち着いてみると700ptぐらいの難易度かも。