Delegation

Explicación

Notemos que si podemos partir el árbol en caminos de al menos $x$ , entonces también podemos partirlo en caminos de al menos $y$ donde $y < x$ . Así, basta con hacer búsqueda binaria sobre la longitud mínima de camino.

Podemos enraizar el árbol de forma arbitraria en el nodo $1$ . Sea $\mathtt{toBeMerged[i]}$ la longitud del camino que pasa por el nodo $i$ y cuya longitud aún no ha sido emparejada. Como solo puede existir uno de esos caminos, todos los demás caminos que provienen de los subárboles de $i$ deben emparejarse de forma pareja con suma de longitudes $\geq k$ .

Queremos maximizar $\mathtt{toBeMerged[i]}$ emparejando de forma pareja a todos los hijos con longitudes de camino $\geq k$ . Para ello, podemos correr otra búsqueda binaria sobre las longitudes de camino no emparejadas de los hijos y comprobar si podemos quitar alguna de ellas y la condición se mantiene. Si quitamos una y el resto sigue sin poder emparejarse, devolvemos falso.

Notemos que esto requiere que el número de longitudes no emparejadas sea inicialmente impar. Si hay un número par de hijos, podemos agregar un $0$ arbitrario. Si nuestra búsqueda binaria devuelve $0$ , entonces sabemos que todos los hijos ya están emparejados de forma pareja.

Implementación

Complejidad temporal: $\mathcal{O}(N \log^2 N)$

C++


#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5;
 
vector<int> g[N];
int to_be_merged[N];
 
// check if elements can be paired with sum >= k
bool check(vector<int> &v, int remove, int k) {
	int l = 0;
	int r = v.size() - 1;
	while (l < r) {
		if (l == remove) { l++; }
		if (r == remove) { r--; }
		if (v[l++] + v[r--] < k) { return false; }
	}
	return true;
}
 
bool dfs(int node, int p, int k) {
	vector<int> v;  // all leftover path lengths from children
	for (int i : g[node]) {
		if (i == p) continue;
		if (!dfs(i, node, k)) return false;
		v.push_back(to_be_merged[i] + 1);
	}
 
	// root edge case
	if (node == 0) {
		// if it is the root, all paths must be evenly paired
		// there must be an even number of paths initially
		if (v.size() % 2 == 1) { v.push_back(0); }
		sort(v.begin(), v.end());
		// return if possible if we do not remove any elements
		return check(v, -1, k);
	}
 
	if (v.size() % 2 == 0) {
		// append dummy 0 (returned if perfectly paired)
		v.push_back(0);
	}
	sort(v.begin(), v.end());
 
	// binary search over the index we can remove
	int l = -1;
	int r = v.size();
	while (l < r - 1) {
		int mid = l + (r - l) / 2;
		// if we remove index mid, can we pair the rest?
		if (check(v, mid, k)) {
			l = mid;
		} else {
			r = mid;
		}
	}
 
	// we cannot pair all paths even if we removed an index
	if (l == -1) { return false; }
 
	to_be_merged[node] = v[l];
	return true;
}
 
int main() {
	ifstream cin("deleg.in");
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		g[--u].push_back(--v);
		g[v].push_back(u);
	}
 
	int l = 0;
	int r = n + 1;
	while (l < r - 1) {
		int mid = l + (r - l) / 2;
		fill(to_be_merged, to_be_merged + n, 0);
		if (dfs(0, 0, mid)) {
			l = mid;
		} else {
			r = mid;
		}
	}
 
	ofstream("deleg.out") << l << endl;
}

Casos de prueba débiles

El siguiente código también obtiene AC debido a datos de prueba débiles, pero técnicamente es $\mathcal{O}(N^2 \log N)$ . Aprovecha el hecho de que podemos cortar en cuanto encontramos un índice para quitar y recorremos linealmente todos los hijos de mayor a menor. Esta solución se puede hackear con un grafo adecuado donde un nodo tiene un gran número de hijos.


#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5;
 
vector<int> g[N];
int to_be_merged[N];
 
// check if elements can be paired with sum >= k
bool check(vector<int> &v, int remove, int k) {
	int l = 0;
	int r = v.size() - 1;
	while (l < r) {
		if (l == remove) { l++; }
		if (r == remove) { r--; }
		if (v[l++] + v[r--] < k) { return false; }
	}
	return true;
}
 
bool dfs(int node, int p, int k) {
	vector<int> v;  // all leftover path lengths from children
	for (int i : g[node]) {
		if (i == p) { continue; }
		if (!dfs(i, node, k)) { return false; }
		v.push_back(to_be_merged[i] + 1);
	}
 
	// root edge case
	if (node == 0) {
		// if it is the root, all paths must be evenly paired
		// there must be an even number of paths initially
		if (v.size() % 2 == 1) { v.push_back(0); }
		sort(v.begin(), v.end());
		// return if possible if we do not remove any elements
		return check(v, -1, k);
	}
 
	if (v.size() % 2 == 0) {
		// append dummy 0 (returned if perfectly paired)
		v.push_back(0);
	}
	sort(v.begin(), v.end());
 
	// linearly search instead of binary searching
	for (int i = v.size() - 1; i >= 0; i--) {
		// check if we were to remove index i, can we pair the rest?
		if (check(v, i, k)) {
			to_be_merged[node] = v[i];
			return true;
		}
	}
	return false;
}
 
int main() {
	ifstream cin("deleg.in");
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		g[--u].push_back(--v);
		g[v].push_back(u);
	}
 
	int l = 0;
	int r = n + 1;
	while (l < r - 1) {
		int mid = l + (r - l) / 2;
		fill(to_be_merged, to_be_merged + n, 0);
		if (dfs(0, 0, mid)) {
			l = mid;
		} else {
			r = mid;
		}
	}
 
	ofstream("deleg.out") << l << endl;
}