AtCoder ARC #152 : D - Halftree

これも割とすんなり解けている。
https://atcoder.jp/contests/arc152/tasks/arc152_d

問題

整数N,Kが与えられる。
N点の無向グラフを考える。
初期状態で辺はない。

ここで任意に辺を追加できるとする。
ただし、頂点対(u,v)間に辺を張ると、同時に((u+K)%N,(v+K)%N)の間にも辺が張られる。

このグラフを木にするような辺の張りかたが可能なら、1例を示せ。

解法

辺の数は偶数なので、まず前提としてNは奇数とする。
またKはNの半分以下と考えてよい。

i＝1～Kに対し、(2nK,2nK+i)間に辺を張ろう。
そうすると2nK～2(n+1)Kが連結となる。
2(n+1)KがN未満である範囲でnを一通り回そう。

これで0～2(n+1)Kが連結となる。
あとは2(n+1)K～(N-1)の間で番号差がKのもの同士を連結しよう。

最後K個未満連続した孤立点が残る。
例えばそのような点がx,yとあるなら、(x,y-K)間に辺を張ると(x+K,y)の間にも辺が張られる。
y-Kやx+Kはすでに連結成分に含まれるので、これで全体が連結状態になる。

int N,K;
vector<pair<int,int>> E;

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 num=um) {int i; FOR(i,num) 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<202020> uf;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	if(N%2==0) {
		cout<<-1<<endl;
		return;
	}
	
	if(K*2>N) K=N-K;
	
	int cur=0;
	while(cur+2*K<N) {
		for(i=1;i<=K;i++) {
			E.push_back({cur,cur+i});
		}
		cur+=2*K;
	}
	
	set<int> S;
	for(i=cur+1;i<N;i++) S.insert(i);
	if(cur+K<N) {
		for(i=1;i<=K;i++) {
			if(cur+K+i<N) {
				E.push_back({cur,cur+i});
				S.erase(cur+i+K);
				S.erase(cur+i);
			}
		}
	}
	while(S.size()) {
		assert(S.size()%2==0);
		x=*S.begin();
		S.erase(x);
		y=*S.begin();
		S.erase(y);
		assert(x+1==y);
		E.push_back({x,y-K});
	}
	
	assert(E.size()*2==N-1);
	if(K*2>N) K=N-K;
	
	FORR2(a,b,E) {
		uf(a,b);
		uf((a+K)%N,(b+K)%N);
	}
	//assert(uf.count(0)==N);
	
	cout<<E.size()<<endl;
	FORR2(a,b,E) cout<<a<<" "<<b<<endl;
	
}

まとめ

これいろいろな解法がありそうだね。