USACO 2020 February Contest, Platinum Problem 1. Delegation

USACO 2020 February Contest, Platinum Problem 1. Delegation

Farmer John's farm consists of NN pastures (2≤N≤1052≤N≤105) connected by N−1N−1 roads, so that any pasture is reachable from any other pasture. That is, the farm is a tree. But after 28 years of dealing with the tricky algorithmic problems that inevitably arise from trees, FJ has decided that a farm in the shape of a tree is just too complex. He believes that algorithmic problems are simpler on paths.

Thus, his plan is to partition the set of roads into several paths and delegate responsibility for these path among his worthy farm hands. He doesn't care about the number of paths. However, he wants to make sure that these paths are all as large as possible, so that no farm hand can get away with asymptotically inefficient algorithms!

Help Farmer John determine the largest positive integer KK such that the roads can be partitioned into paths of length at least KK.

 

 

 

 

SAMPLE INPUT:

8
1 2
1 3
1 4
4 5
1 6
6 7
7 8

SAMPLE OUTPUT:

3

One possible set of paths is as follows:

 

Problem credits: Mark Gordon and Dhruv Rohatgi

USACO 2020 February Contest, Platinum Problem 1. Delegation 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Root the tree at 11. We will do DP on subtrees.

It suffices to binary search on K.K. We should write a function DFS(x)DFS(x) which partitions the subtree corresponding to vertex xx into paths of length at least KK and possibly an extra one with one endpoint at xx which might have length less than KK. If the subtree can be partitioned, this function will return the maximum possible length of the extra path. Otherwise, the function will return −1−1, meaning that it is impossible to divide the tree.

First, we should call DFS(t)DFS(t) for all children tt of x.x. If any of these return −1,−1, then DFS(x)DFS(x) should also return −1.−1. Otherwise, we have a path of length DFS(t)+1DFS(t)+1 with one endpoint at x.x.

Suppose that we want to check whether we can pair up all the child paths of xx such that all paths have length at least KK. To do this, sort the path lengths in increasing order and repeatedly pair the least and the greatest lengths. If there are an odd number of path lengths, we should add 00 to the beginning of this list before pairing.

Otherwise, one child path will be left unpaired, and we would like to maximize the length of this path. Note that if it is possible to end up with an extra path of length x,x, then for all y<xy<x it is also possible to end up with an extra path of length y.y. Thus, we can binary search again to find the maximum possible x.x.

In summary, DFS(x)DFS(x) will return the maximum possible length of an extra path if possible. Otherwise, if we can pair up all child paths, DFS(x)DFS(x) will return 0.0. Otherwise, it is not possible to generate paths such that all have length at least K,K, so DFS(x)DFS(x) should return −1.−1.

This solution runs in O(Nlog2N)O(Nlog2⁡N) time.

 

#include "bits/stdc++.h"

using namespace std;

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

#define f first
#define s second

const int MOD = 1e9+7;
const int MX = 1e5+5;

int N,K;
vector<int> adj[MX];
bool bad = 0;
 
bool ok(const vector<int>& V, int mid) {
	int l = 0, r = (int)V.size()-1;
	for (int i = 0; i < V.size()/2; ++i) {
		if (l == mid) l ++;
		if (r == mid) r --;
		if (V[l]+V[r] < K) return 0;
		l ++, r --;
	}
	return 1;
}
 
int DFS(int x, int y) {
	if (bad) return -1;
	vector<int> v; 
	for (auto t: adj[x]) if (t != y) {
		int d = DFS(t,x)+1; if (bad) return -1;
		v.push_back(min(K,d));
	}
	sort(begin(v),end(v));
	bool al = 1;
	int mx = -MOD;
	{
		auto V = v; if (V.size()&1) V.insert(V.begin(),0);
		al = ok(V,-1);
	}
	{
		auto V = v; if (!(V.size()&1)) V.insert(V.begin(),0);
		int lo = -1, hi = V.size()-1;
		while (lo < hi) {
			int mid = (lo+hi+1)/2;
			if (ok(V,mid)) lo = mid;
			else hi = mid-1;
		}
		if (lo >= 0) mx = V[lo];
	}
	if (x == 1) {
		if (!al) bad = 1;
		return -1;
	}
	if (mx != -MOD) return mx;
	if (al) return 0;
	bad = 1; return -1;
}
 
bool SOLVE(int k) {
	K = k; bad = 0; DFS(1,0);
	return !bad;
}
 
void SOLVE() {
	int lo = 1, hi = N-1;
	while (lo < hi) {
		int mid = (lo+hi+1)/2;
		if (SOLVE(mid)) lo = mid;
		else hi = mid-1;
	}
	cout << lo << "\n";
}
 
int main() {
	// setIO(); 
	cin >> N;
	for (int i = 1; i < N; ++i) {
		int a,b; cin >> a >> b;
		adj[a].push_back(b), adj[b].push_back(a);
	}
	SOLVE();
}

[/hide]