Codeforces #688 Div2 E. Dog Snacks

これはちょっと手間取ったけど普通に解けた。
https://codeforces.com/contest/1453/problem/E

問題

根付き木が与えられる。
各点にはお菓子が置いてあるので、根頂点にいるプレイヤーはそれを回収したい。
プレイヤーは以下のように動く。

• お菓子が置いてある頂点のうち、最寄りの頂点に移動しそのお菓子を回収する。同じ距離の頂点があれば1つ選択してよい。
  • ただし、距離kを超える移動はできない。
• 最後のお菓子を食べた後、根頂点に移動する。ただしこちらも距離kを超える移動はできない。

条件を満たす最小のkを求めよ。

解法

二分探索で求める。
各頂点でDFSし、各頂点のSubTreeのうち最も浅い葉を最後に到達して戻るようにしよう。
その際、その葉のある子頂点以外の子頂点については、その先に潜っていっても戻ってこれることを確認しよう。
(具体的には各子頂点の先の浅い葉までの距離がk-1以下ならよい)

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

int dfs(int cur,int pre,int d,int b) {
	
	if(cur&&E[cur].size()==1) return d;
	
	vector<int> V;
	FORR(e,E[cur]) if(e!=pre) V.push_back(dfs(e,cur,d+1,b));
	sort(ALL(V));
	int once=1;
	while(V.size()>=2) {
		int y=V.back();
		V.pop_back();
		
		if(cur==0&&y==b&&once) {
			once=0;
			V.insert(V.begin(),y);
			continue;
		}
		
		if((y-d+1)>b) return 1<<30;
	}
	return V[0];
	
}

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);
		}
		
		int ret=N;
		for(i=20;i>=0;i--) if(ret-(1<<i)>=1&&dfs(0,-1,0,ret-(1<<i))<=(ret-(1<<i))) ret-=1<<i;
		cout<<ret<<endl;
	}
}

まとめ

単なる木や根付き木だけを対象とした問題、よくいろいろ作れるよなぁとは思う。