Codeforces ECR #166 : F. Remove Bridges

ボス問の割にはコードが短い。
https://codeforces.com/contest/1976/problem/F

問題

根付き木が与えられる。
ここに徐々に辺を追加できるとき、以下のようにしたい。

• 橋の数を最小化する
• 橋があるとき、その低い側の点のsubtreeの辺はいずれも橋

辺を1～(N-1)個まで追加するとき、それぞれ残る橋の数を答えよ。

解法

追加する辺の両端は、根か葉である。
辺を追加すると、元々その両端を結んでいた点同士パスが、橋ではなくなる。
よってその数が最少となるように1点ずつ選ぼう。

int T,N;
vector<int> E[303030];

int D[303030];
int dfs(int cur,int pre) {
	D[cur]=0;
	FORR(e,E[cur]) if(e!=pre) D[cur]=max(D[cur],dfs(e,cur)+1);
	return D[cur];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			E[i].clear();
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		
		dfs(0,0);
		set<pair<int,int>> S;
		FOR(i,N) S.insert({D[i],i});
		vector<int> ret;
		
		int cur=N;
		while(S.size()) {
			x=S.rbegin()->second;
			
			while(1) {
				cur--;
				S.erase({D[x],x});
				if(D[x]==0) break;
				FORR(e,E[x]) if(D[e]==D[x]-1) {
					x=e;
					break;
				}
			}
			ret.push_back(cur);
		}
		FOR(i,2*N) ret.push_back(0);
		FOR(i,N-1) cout<<ret[2*i]<<" ";
		cout<<endl;
	}
}

まとめ

この回7問でもよさそうな難易度。