Codeforces #872 : Div1 B2. LuoTianyi and the Floating Islands (Hard Version)

Bで手間取りすぎてひどい出来だった回。
https://codeforces.com/contest/1824/problem/B2

問題

N頂点の木を成すグラフと、整数Kが与えられる。
N頂点からK点を選ぶ。
N個の点のうち、K点への距離の総和が最小値と一致する頂点の数の期待値を求めよ。

解法

各点について、その各隣接点の先に過半数となる頂点数が選ばれていない場合に、条件を満たす点となる。

• Kが奇数の時は1。というのも、K点を含む最小の部分誘導グラフを考えると、その重心一択になる。
• Kが偶数の場合、各点の先にある頂点数を考え、特定の辺の先に過半数の頂点が選択されるケースを累積和の要領で数え上げよう。

int N,K;
const ll mo=1000000007;
vector<int> E[202020];
int C[202020];
ll P[202020];
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		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;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}


ll ret=0;
int dfs(int cur,int pre) {
	vector<int> V={1};
	C[cur]=1;
	FORR(e,E[cur]) if(e!=pre) {
		int x=dfs(e,cur);
		V.push_back(x);
		C[cur]+=x;
	}
	V.push_back(N-C[cur]);
	
	//過半数行くケース
	
	FORR(v,V) {
		int L=K/2+1;
		int R=min(v,N-(K/2-1));
		if(L<=R) {
			P[L]++;
			P[R+1]--;
		}
	}
	
	return C[cur];
	
}

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

まとめ

今考えるとそこまで難しくもないのだが、なんで本番こんな苦戦してるんだ。