My solution to all the CSES Tree Algorithms Problems.
Problems available at : https://cses.fi/problemset/list/
-
Subordinates : Dynamic Programming to calculate subtree size rooted at each node.
-
Tree Matching : Dynamic Programming on Trees.
-
Tree Diameter : 1st solution based on Proof of Diameter. 2nd using Dynamic Programming on Trees where we try all possible paths.
-
Tree Distances I : Dynamic Programming on Trees + Rerooting Technique.
-
Tree Distances II : Dynamic Programming on Trees + Rerooting Technique.
-
Company Queries I : Binary Lifting(which in itself is a Dynamic Programing Approach).
-
Company Queries II : Answer LCA queries in O(logn) Time Using Binary Lifting . (Note: Binary Search + Binary Lifting Will give TLE because it will be O(log2n) per query ).
-
Distance Queries : Binary Lifting.