Codeforces #810 : Div1 D. Recover the Tree

この問題記憶にないな…。
https://codeforces.com/contest/1710/problem/D

問題

N頂点の木を成す無向グラフがある。
頂点の区間[L,R]に対し、その区間内の頂点からなる誘導部分グラフが連結かどうかが情報として与えられる。
元のグラフを再構成せよ。

解法

区間の小さい順に処理して行く。
今点iの含まれる連結成分が[L[i],R[i]]とする。
もしxとyが非連結なのに、区間[x,y]が連結であることが分かった場合、[L[x],R[y]]が連結になることになる。
その際、[L[x],R[y]]がx-y間の辺を含める前に[L0,R0],[L1,R1],....,[Ln,Rn]のような連結成分があった場合、
....L5-L3-L1-x-y-L0-L2-L4....のような辺があったと考えることができる。

int T,N;
int C[2020][2020];

int L[2020],R[2020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		FOR(i,N) {
			cin>>s;
			FOR(j,N-i) C[i][i+j]=s[j]=='1';
			L[i]=R[i]=i;
		}
		vector<pair<int,int>> V;
		for(int len=1;len<=N;len++) {
			for(x=0;x+len<N;x++) {
				y=x+len;
				if(C[x][y]==0||L[x]==L[y]) continue;
				int X=x;
				int Y=y;
				V.push_back({x,y});
				int t=R[x]+1;
				int turn=1;
				while(t<L[y]) {
					if(turn) {
						V.push_back({t,Y});
						Y=t;
					}
					else {
						V.push_back({t,X});
						X=t;
					}
					turn^=1;
					t=R[t]+1;
				}
				
				
				int a=L[x];
				int b=R[y];
				for(j=a;j<=b;j++) L[j]=a, R[j]=b;
				
			}
		}
		assert(V.size()==N-1);
		FORR2(a,b,V) cout<<a+1<<" "<<b+1<<endl;
	}
}

まとめ

実装は軽いけど、考察が難しいな。