Official Analysis (C++)

Explanation

Note that if we can split the tree into paths of at least $x$, then we can also split it into paths of at least $y$ where $y < x$. Thus, it suffices to binary search over the minimum path length.

We can arbitrarily root the tree at node $1$. Let $\mathtt{toBeMerged[i]}$ store the length of the path passes through node $i$ and its length has not been paired yet. Since only one of such path can exist, all of the other paths which source from the subtrees of $i$ must be evenly paired with sum of lengths $\geq k$.

We want to maximize $\mathtt{toBeMerged[i]}$ while evenly pairing all of the children with path lengths $\geq k$. To do this, we can run another binary search over the unpaired path lengths of the children and check if we can remove any of them and the condition holds. If we removed one and the rest is still unpairable, then we return false.

Note that this requires the number of unpaired lengths to be initially odd. If there are an even number of children, then we can append an arbitrary $0$. If our binary search returns $0$, then we know all the children are already evenly paired.

Implementation

Time Complexity: $\mathcal{O}(N \log^2 N)$

Copy
#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) {

Copy
#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) {