Java
Java copied to clipboard
Feature/centroid decomposition
- [ x] I have read CONTRIBUTING.md.
- [ x] This pull request is all my own work -- I have not plagiarized it.
- [ x] All filenames are in PascalCase.
- [x ] All functions and variable names follow Java naming conventions.
- [ x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [ x] All new code is formatted with
clang-format -i --style=file path/to/your/file.java
Summary: This PR adds an implementation of centroid decomposition for trees. The algorithm recursively finds centroids of subtrees and builds a centroid tree with height O(log n). This structure is useful for answering distance, nearest node, and other divide and conquer tree queries.
Details:
Supports adding edges to an undirected tree
Builds the centroid decomposition via build()
Provides access to centroid parents and children
Includes a helper to iterate over centroid ancestors
Tests cover subtree sizes, parent relationships, children, reset behaviour, and consistency