Delegation

Explicación

Primero, notemos que si $K$ no es un divisor de $N - 1$ , entonces las aristas nunca se pueden particionar de forma pareja. Así, solo necesitamos revisar los divisores de $N - 1$ .

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 todavía no llegó a $K$ . Como solo existe $1$ camino así, todos los demás caminos que provienen de los subárboles de $i$ deben emparejarse de forma pareja.

Para cada nodo $j$ tal que $j$ es hijo del nodo $i$ , debe existir otro nodo $k$ tal que $\mathtt{toBeMerged[j]+toBeMerged[k]} + 2 = K$ para completar el camino. Si no existe tal $k$ , entonces guardamos la longitud actual del camino en $\mathtt{toBeMerged[i]}$ , pero solo puede haber un $j$ así.

el arbol

En el árbol de arriba, supongamos $K = 3$ . Entonces $\mathtt{toBeMerged[2]} = 2$ , $\mathtt{toBeMerged[5]} = 1$ , $\mathtt{toBeMerged[7]} = 0$ y $\mathtt{toBeMerged[8]} = 0$ . Como hay dos caminos de longitud $0$ y solo uno de longitud $1$ , nos queda un camino de longitud $0$ , así que $\mathtt{toBeMerged[1]} = 0 + 1 = 1$ .

Se puede demostrar que el número máximo de divisores de un entero hasta las restricciones de $N$ será lo suficientemente pequeño como para ejecutar un algoritmo de tiempo lineal por cada divisor.

Implementación

Complejidad temporal: $\mathcal{O}(N \cdot N^{o(1)})$

C++


#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5;
vector<int> g[N];
int to_be_merged[N];
 
bool dfs(int node, int p, int k) {
	// contamos la longitud del camino aún no fusionado en los subárboles
	map<int, int> to_be_merged_count;
 
	for (int i : g[node]) {
		if (i == p) { continue; }
		if (!dfs(i, node, k)) { return false; }
		int cur_merge = to_be_merged[i] + 1;
		if (cur_merge != k) { to_be_merged_count[cur_merge]++; }
	}
 
	/*
	 * todos los subárboles deben emparejarse excepto uno, donde la longitud
	 * del camino se guarda en to_be_merged[node]
	 */
	for (auto [key, value] : to_be_merged_count) {
		if (key == k - key) {
			// fusionamos caminos de longitud k / 2
			if (value % 2 == 1) {
				// hay un camino sobrante
				if (to_be_merged[node]) { return false; }
				to_be_merged[node] = key;
			}
		} else {
			// fusionamos caminos cuyas longitudes suman k
			if (value > to_be_merged_count[k - key]) {
				// hay más de un camino o ya encontramos un camino
				if (value - to_be_merged_count[k - key] > 1 || to_be_merged[node]) {
					return false;
				}
				// guardamos el camino sobrante
				to_be_merged[node] = key;
			}
		}
	}
 
	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);
	}
 
	ofstream cout("deleg.out");
	for (int k = 1; k <= n - 1; k++) {
		if ((n - 1) % k != 0) {
			cout << 0;
		} else {
			fill(to_be_merged, to_be_merged + n, 0);
			cout << dfs(0, 0, k);
		}
	}
}