Codeforces ECR #106 : F. Diameter Cuts

まぁこれは解法がわかりやすいな…。
https://codeforces.com/contest/1499/problem/F

問題

N頂点の木を成す無向グラフが与えられる。
ここからいくつか辺を取り除き、残された各連結成分の直径がK以下となるようにしたい。
辺の取り除き方は何通りか。

解法

各頂点vに対し、以下の値を考える。
f(v, n) := vのsubtree内でいくつか辺を取り除いた時、直径がKを超える連結成分がなく、かつvからつながる最長パスの長さがnであるような取り除き方の組み合わせ
あとは各頂点をDFSし、子頂点との間の辺を残す場合と消す場合のf(v,n)の変化を考えていくとよい。

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

void dfs(int cur,int pre) {
	vector<ll> A={1};
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		pat[e].insert(pat[e].begin(),0);
		
		vector<ll> B(max(A.size(),pat[e].size()));
		int a,b;
		FOR(a,A.size()) FOR(b,pat[e].size()) {
			// connect
			if(a+b<=K) (B[max(a,b)]+=A[a]*pat[e][b])%=mo;
			// disconnect
			if(a<=K) (B[a]+=A[a]*pat[e][b])%=mo;
		}
		swap(A,B);
	}
	pat[cur]=A;
}

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);
	}
	
	dfs(0,0);
	ll ret=0;
	FOR(i,pat[0].size()) if(i<=K) ret+=pat[0][i];
	cout<<ret%mo<<endl;
}

まとめ

考察も実装もそこまで難しい問題ではない気がするが、妙にAC数が少ないな。
Dの正答者が少ないから、そこで詰まった人が多かったのかな。