Codeforces ECR #074 : F. The Maximum Subtree

問題の理解に若干手間取った。
https://codeforces.com/contest/1238/problem/F

問題

K個の1次元空間があったとき、以下のようにグラフを作ることを考える。
K個の各空間に対し頂点を割り当てる。対応する空間に共通部分がある場合に辺を張る。

ここで、ある木を成すグラフが与えられる。
この部分グラフとして、上記割り当て方で生成できるような最大の部分着のサイズを求めよ。

解法

ある木のSubTreeに対し条件を満たしてどこまで大きいものを作れるか考える。

• 子頂点が1個もないなら、サイズ1。
• 子頂点が1個だけあるなら、子頂点以下からなるところにサイズ+1。孫頂点に対応する区間は子を全部覆わないはずなので、そこに現頂点に対応する区間を置ける。
• 子頂点が2個あるなら、両端に最大サイズの子頂点以下のグラフを置き、それ以外は子頂点だけを配置して孫頂点以下は無視する。

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

int ma;
int dfs(int cur,int pre) {
	vector<int> V;
	FORR(e,E[cur]) if(e!=pre) V.push_back(dfs(e,cur));
	sort(ALL(V));
	reverse(ALL(V));
	
	if(V.size()>=2) {
		ma=max(ma,(int)(V[0]+V[1]+1+V.size()-2+(pre!=-1)));
		return V[0]+1+V.size()-1;
	}
	else if(V.size()==1) {
		ma=max(ma,V[0]+1);
		return V[0]+1;
	}
	else {
		if(pre!=-1) ma=max(ma,2);
		return 1;
	}
}

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);
		}
		ma=1;
		dfs(0,-1);
		cout<<ma<<endl;
	}
}

まとめ

ECRのFにしては実装が軽い。