Grakn Forces 2020 : G. Clusterization Counting

これまたMerge順を木にする奴か。
https://codeforces.com/contest/1408/problem/G

問題

N個の点があるグラフを考える。
2頂点対毎のコストが与えられる。
このコストは、頂点対ごとに異なっている。

この頂点群を、K個のグループに分解することを考える。
その際、各グループにおいてグループ内の頂点対のコストの最大値は、グループ内の点とグループ外の点のコストの最小値より小さくなければならない。

K=1～Nに対し、条件を満たすグループの分け方は何通りか。

解法

クラスカル法の要領で、頂点を連結していく。
その際、辺を追加するだけではなく、連結時に毎回新規頂点を作ろう。

また、もしすでに連結状態の頂点対に新規に辺を追加する場合、辺の数を数えることで完全グラフになっているかを判定する。
完全グラフであれば、その(連結時に生成した)頂点に対応する頂点群は、単一のグループを構成できることを意味する。
（言い換えると、この連結成分の外と結ぶ辺は、これより大きなコストの辺しかないことになるので、問題文の条件を満たす）

あとはこの全域木に対し木DPで、その頂点のSubTree内でk個のグループを構成できるのは何通りかを数えていけばよい。

int N;
int A[2020][2020];
const ll mo=998244353;
int cand[1515*1515];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

UF<3200> uf;
int V[3000];
int E[3000];
int P[3030];
vector<int> C[3030];
int ok[3030];

ll dp[3030][1600];


void dfs(int cur) {
	if(ok[cur]) dp[cur][1]=1;
	if(C[cur].size()) {
		int a=C[cur][0];
		int b=C[cur][1];
		int x,y;
		dfs(a);
		dfs(b);
		for(x=1;x<=V[a];x++) for(y=1;y<=V[b];y++) {
			(dp[cur][x+y]+=dp[a][x]*dp[b][y])%=mo;
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int ma=0;
	FOR(y,N) FOR(x,N) {
		cin>>A[y][x];
		ma=max(ma,A[y][x]);
		if(A[y][x]) cand[A[y][x]-1]=y*2000+x;
	}
	FOR(i,N) V[i]=1,P[i]=i,ok[i]=1;
	int nex=N;
	FOR(i,ma) {
		x=cand[i]%2000;
		y=cand[i]/2000;
		x=uf[x];
		y=uf[y];
		if(x==y) {
			r=P[x];
			E[r]++;
			if(E[r]==V[r]*(V[r]-1)/2) {
				ok[r]=1;
			}
		}
		else {
			C[nex].push_back(P[x]);
			C[nex].push_back(P[y]);
			uf(x,y);
			V[nex]=V[P[x]]+V[P[y]];
			E[nex]=E[P[x]]+E[P[y]]+1;
			if(E[nex]==V[nex]*(V[nex]-1)/2) {
				ok[nex]=1;
			}
			P[x]=P[y]=nex;
			nex++;
		}
	}
	dfs(nex-1);
	
	for(i=1;i<=N;i++) cout<<dp[nex-1][i]<<" ";
	cout<<endl;
	
	
}

まとめ

3000ptにしては簡単。