What is the initialization time of a link-cut tree?
Many thanks to Hsueh-I Lu, my teacher in National Taiwan University, who provides the following solution.

It turns out that the answer is rather simple; in the initialization of a data structure, we don't have to construct the structure by the queries and operations it supports. Of course, we cannot perform queries during the construction like we usually do if we build the tree by link operation; but in this separator decomposition application we don't need it.

That is to say, in the application to the separator decomposition, when we have to construct the link-cut trees L(T) for the spanning tree T on input graph G, instead of computing the structures and values of the trees L(T) by link operation, we directly compute the heavy-light path decomposition of the tree T, and construct the corresponding binary tree structure for each paths, and gluing the binary trees according to the path decomposition. All the steps can be done in linear time.

For each necessary values on the nodes of L(T), since each value can be compute from T in linear time (in this application), instead of assigning values on binary tree structures and updating when gluing the trees, we assign the precomputed values directly onto the nodes of the final link-cut trees L(T). There are only a constant type of values need to be assigned, and again this can be done in linear time.