In this paper, we consider the problem of maintaining the centdians in a fully dynamic forest. A forest is said to be fully dynamic if edge insertions, edge deletions, and changes of vertex weights are allowed. Centdian is a specific kind of facility that integrates the notions of center and median by taking a convex combination on the objective functions of both problems. This work extends the results in Alstrup et al.  within the same time complexity, i.e., linear time preprocessing and O(logn) per update, where n is the number of vertices of the components being updated.
ASJC Scopus subject areas