I just used an existing implementation and added some extra bookkeeping data to be able to recompute the regularization quickly. The $$$\gamma$$$ is the "resolution" and is just a parameter for the objective function (for modularity, $$$\gamma = \frac1{2|E|}$$$).

For the local search, let $$$S$$$ be the current best score and $$$S'$$$ be the score after a proposed change. If $$$S \gt S'$$$, my algorithm would accept the change with probability $$$\min(0.02, \exp(10(S'-S))$$$. The proposed change was the best change among all possible moves for 55 randomly sampled nodes. There's no reason for choosing any of these parameters, it just worked well enough in practice.

My best solutions came from applying the Leiden algorithm adapted to fit the objective function, coupled with some local search/simulated annealing to get a few dozen extra points.

Can B be solved without a fast factoring method (eg. Pollard rho)?

Nisiyama_Suzune's excellent blog on Möbius inversion describes this exact problem.

You can also solve the problem in $$$O(n)$$$ with Möbius inversion and a linear-time sieve.

The expected depth of recursion is actually $$$O(\sqrt n)$$$ (Knuth, p. 15). Page 13 of the same article gives an algorithm to generate bracket sequences (and thus also binary trees) which runs in $$$O(n)$$$ time and uses numbers not larger than $$$O(n^2)$$$.

Correct me if I'm wrong, but I think that generating a random labeled tree with Prüfer codes, choosing the root randomly, and ordering children according to their label should give a rooted tree with ordered children generated uniformly at random. I haven't proved it, but it should work (it should be the same as ordering children randomly).

EDIT: it can't be correct since $$$C_{n-1}$$$ does not divide $$$n^{n-2}$$$.

Given a rooted tree $$$T$$$ with ordered children, we can construct a rooted binary tree $$$B$$$ by making $$$u$$$'s left child in $$$B$$$ its first child in $$$T$$$, and $$$u$$$'s right child in $$$B$$$ the next sibling in order in $$$T$$$. Conversely, we can perform the reverse operation to turn a binary tree into a rooted tree. Thus each binary tree corresponds to one rooted tree and vice versa, so the given problem is equivalent to generating a rooted tree (with ordered children) uniformly at random, since we can convert freely between the two without losing any information.

The Wikipedia page has some pictures that might help visualize the transformation.

There is a one-to-one correspondence between rooted binary trees and rooted trees with ordered children (left child <-> left child, right child <-> right sibling). We can generate a rooted tree with ordered children uniformly at random using Prüfer codes then convert it to a binary tree.

EDIT: it doesn't work

I think it should be possible to process all queries offline using the smaller-to-larger optimization.