(Analysis by Benjamin Qi)

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

First, observe that the answer is "no" if $N-1$ is not divisible by $K.$ Otherwise, we wish to write a function $dfs(x)$ which will check whether it is possible to partition the subtree corresponding to vertex $x$ into paths of length $K$ and possibly an extra one of length less than $K$ with one endpoint at $x$. If possible, this function will return the length of the extra path. Otherwise, the function will return $-1$.

First, we should call $dfs(t)$ for all children $t$ of $x.$ If any of these return $-1,$ then $dfs(x)$ should also return $-1.$ Otherwise, we have a path of length $dfs(t)+1$ with one endpoint at $x.$ After doing this, we should pair up as many of the paths whose lengths are in $(0,K)$ as possible. If there is more than one unpaired path remaining after this process, return $-1$.

Otherwise, return the length of the unpaired path, or zero if none exists. Note that if $dfs(x)\neq -1,$ then its return value is equal to the remainder when the number of edges in the subtree corresponding to $x$ is divided by $K,$ which is invariant regardless of how exactly we choose the paths of length $K$.

For a fixed $K,$ we can check whether it is possible to split the tree into paths of length $K$ in $O(N)$ time, allowing us to solve the problem in $O(N\cdot (\#\text{ of divisors of }N)).$ However, several solutions with this complexity ended up receiving TLE on test case $3$, where $N=83161$ and $N-1$ has $128$ divisors. One option is to deal with the star case separately. Another is to write a checker that does not use recursion and is a constant factor faster, demonstrated below.

#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,sub[MX];

void dfs(int a, int b) {
sub[a] = 1;
for(auto& t: adj[a]) if (t != b) {
dfs(t,a);
sub[a] += sub[t];
num[a].push_back(sub[t]);
}
if (sub[a] != N) num[a].push_back(N-sub[a]);
}

int cur[MX]; // basically unordered map
bool ok(int K) {
if ((N-1)%K != 0) return 0;
for (int i = 0; i < K; ++i) cur[i] = 0;
for (int i = 1; i <= N; ++i) {
int cnt = 0;
for (auto& t: num[i]) {
int z = t%K; if (z == 0) continue;
if (cur[K-z]) cur[K-z] --, cnt --;
else cur[z] ++, cnt ++;
}
if (cnt) return 0; // paths don't pair up
}
return 1;
}

int main() {
setIO("deleg");
cin >> N;
for (int i = 1; i < N; ++i) {
int a,b; cin >> a >> b;