Codeforces #633 Div1 D. Nested Rubber Bands

本番妙にsystestで落ちた人が多かった問題。
https://codeforces.com/contest/1338/problem/D

問題

N頂点からなる木を成すグラフが与えられる。
このグラフをもとに、平面上に頂点に対応したN個の閉曲線を配置することを考える。
元のグラフで辺を持つ頂点同士は、平面上で閉曲線が交差するようにしたい。
反対に、辺を持たない頂点同士は対応する閉曲線が交差しないようにしたい。
最大で閉曲線同士が何階層ネストさせることができるか。

解法

頂点vに対し、隣接点cがいくつかあったとする。
すると、このc同士は任意の順でネストさせるようにできる。
例えばk個の頂点c(0)～c(k-1)に対応する閉曲線がこの順で外側から内側にネストしているとする。

この時、c(0)からはc(1)以外の隣接点に対応する閉曲線をさらに外側にネストできるし、c(k-1)からはc(k-2)以外の隣接点ん位対応する閉曲線をさらに内側にネストできる。

言い換えると、距離が2以上ある点はネスト関係にできるので、そのようなものを数え上げて行こう。

int N;
vector<int> E[202020];
int ma;

int dp[101010][2];

void dfs(int cur,int pre) {
	int NC=E[cur].size()-(pre!=-1);
	int m[2]={0,0};
	vector<int> P[2];
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		P[0].push_back(dp[e][0]);
		P[1].push_back(dp[e][1]);
		// not take
		ma=max(ma,max(m[0],m[1])+max(dp[e][0],dp[e][1])+(int)E[cur].size()-2);
		
		// take
		ma=max(ma,m[0]+dp[e][0]+1);
		m[0]=max(m[0],dp[e][0]);
		m[1]=max(m[1],dp[e][1]);
	}
	
	dp[cur][0]=max(0,max(m[0],m[1])+NC-1);
	dp[cur][1]=1+m[0];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) if(E[i].size()>1) {
		dfs(i,-1);
		break;
	}
	cout<<ma<<endl;
}

まとめ

Div1Dの割には簡単。