Home » 国际竞赛 » Details

USACO 2020 February Contest, Platinum Problem 1. Delegation

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午2:49

USACO 2020 February Contest, Platinum Problem 1. Delegation

Farmer John's farm consists of? $N$ ?pastures ( $2 \leq N \leq 10^{5}$ ) connected by? $N - 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? $K$ ?such that the roads can be partitioned into paths of length at least? $K$ .

SCORING:

In test cases 2-4 the tree forms a star; at most one vertex has degree greater than two.
Test cases 5-8 satisfy? $N \leq 10^{3}$ .
Test cases 9-15 satisfy no additional constraints..

INPUT FORMAT (file deleg.in):

The first line contains a single integer? $N$ .The next? $N - 1$ ?lines each contain two space-separated integers? $a$ ?and? $b$ ?describing an edge between vertices? $a$ ?and? $b$ . Both? $a$ ?and? $b$ ?are in the range? $1 \dots N$ .

OUTPUT FORMAT (file deleg.out):

Print? $K$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

One possible set of paths is as follows:

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

Problem credits: Mark Gordon and Dhruv Rohatgi

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

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Root the tree at? $1$ . We will do DP on subtrees.

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

First, we should call? $D F S (t)$ ?for all children? $t$ ?of? $x .$ ?If any of these return? $- 1,$ ?then? $D F S (x)$ ?should also return? $- 1.$ ?Otherwise, we have a path of length? $D F S (t) + 1$ ?with one endpoint at? $x .$

Suppose that we want to check whether we can pair up all the child paths of? $x$ ?such that all paths have length at least? $K$ . 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? $0$ ?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,$ ?then for all? $y < x$ ?it is also possible to end up with an extra path of length? $y .$ ?Thus, we can binary search again to find the maximum possible? $x .$

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

This solution runs in? $O (N \log^{2} 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]