Hello Codeforces,

Introduction

I came across this problem a while back — https://cses.fi/problemset/task/1139/. Here the task is — "Given a rooted tree, determine the number of distinct elements for each subtree of the tree". It is possible to solve this problem by flattening the tree and then using a binary indexed tree(now that subtrees have converted into subarrays). I will discuss an alternate technique to solve this which can help in cases where it is useful to have the entire subtree as a set in a dfs call.

$$$O(n^2)$$$ solution

If $$$n$$$ were small, we could have stored for each node, the set of elements in its subtree. A DFS can be used to evaluate this which will take $$$O(n^2log n)$$$ time and $$$O(n^2)$$$ space.