Centroid Decomposition - O(n log n + m log m) solution
Intuition\n- For a tree with size n, the key task is to find for each node the number of nodes with distance  \leq k.\n- Centroid decomposition is an efficient 
# Intuition\n- For a tree with size $$n$$, the key task is to find for each node the number of nodes with distance  $$\\leq k$$.\n- Centroid decomposition is an efficient algorithm dealing with distances between any two nodes in a tree. A centroid is a node such that when being the root, no subtree has size $$\\geq n/2$$. After finding a centroid for a tree, we recursively repeat it for the subtrees, resulting in at most $$O(\\log n)$$ centroids.\n- Note that any simple path between two nodes in a tree must pass through a common centroid ancestor, going from one subtree to another subtree. The distance between the two nodes is simply the sum of the distances from the centroid to the two nodes. \n\n# Approach\nWe iterate through each centroid. For each centroid, we first find the distances from the centroid to the nodes in each subtree, and count the frequencies. For each node in a subtree, we only need to consider the paths from that node to the centroid, then going into any other subtrees. The number of such paths with length $$\\leq k$$ can be obtained using prefix sums. Note that all these computations take $$O(n)$$ time for each centroid.\n\n# Complexity\n- Time complexity:\n$$O(n\\log n+m\\log m)$$\n\n- Space complexity:\n$$O(n+m)$$\n\nThe below code takes around 200 ms.\n\n# Code\n```python3 []\nfrom collections import defaultdict\n\nclass Solution:\n    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]], k: int) -> List[int]:\n        def subtreeSizes(node, parent):\n            nonlocal sizes\n            for child in adj[node]:\n                if child == parent or child in visited:\n                    continue\n                sizes[node] += subtreeSizes(child, node)\n            return sizes[node]\n\n        def findCentroid(node, parent, root):\n            for child in adj[node]:\n                if child == parent or child in visited:\n                    continue\n                if sizes[child] > sizes[root] // 2:\n                    return findCentroid(child, node, root)\n            return node\n\n        def findDistances(node, parent, depth, count):\n            if depth > k:\n                return\n            if len(count) == depth - 1:\n                count.append(1)\n            else:\n                count[depth - 1] += 1\n            for child in adj[node]:\n                if child == parent or child in visited:\n                    continue\n                findDistances(child, node, depth + 1, count)\n\n        def countTarget(node, parent, depth, total, curr):\n            if depth > k:\n                return\n            nonlocal result\n            result[node] += total[min(k - depth, len(total) - 1)] - curr[min(k - depth, len(curr) - 1)]\n            for child in adj[node]:\n                if child == parent or child in visited:\n                    continue\n                countTarget(child, node, depth + 1, total, curr)\n\n        def centroidDecomposition(node):\n            nonlocal visited, result, sizes\n            sizes = [1] * n\n            subtreeSizes(node, -1)\n            centroid = findCentroid(node, -1, node)\n            visited.add(centroid)\n            prefixes = {}\n            maxlen = 1\n            for child in adj[centroid]:\n                if child in visited:\n                    continue\n                count = []\n                findDistances(child, centroid, 1, count)\n                prefixes[child] = [0]\n                for i in range(len(count)):\n                    prefixes[child].append(prefixes[child][-1] + count[i])\n                maxlen = max(maxlen, len(prefixes[child]))\n            total = [1] * maxlen\n            for child in prefixes:\n                for i in range(maxlen):\n                    total[i] += prefixes[child][min(i, len(prefixes[child]) - 1)]\n            result[centroid] += total[min(k, len(total) - 1)]\n            for child in adj[centroid]:\n                if child in visited:\n                    continue\n                countTarget(child, centroid, 1, total, prefixes[child])\n            for child in adj[centroid]:\n                if child in visited:\n                    continue\n                centroidDecomposition(child)\n\n        k -= 1\n        if k < 0:\n            maxcount = 0\n        else:\n            adj = defaultdict(list)\n            for edge in edges2:\n                adj[edge[0]].append(edge[1])\n                adj[edge[1]].append(edge[0])\n            n = len(edges2) + 1\n            sizes = []\n            visited = set()\n            result = [0] * n\n            centroidDecomposition(0)\n            maxcount = max(result)\n        k += 1\n        adj = defaultdict(list)\n        for edge in edges1:\n            adj[edge[0]].append(edge[1])\n            adj[edge[1]].append(edge[0])\n        n = len(edges1) + 1\n        sizes = []\n        visited = set()\n        result = [maxcount] * n\n        centroidDecomposition(0)\n        return result\n```
['Python3']