classSolution: defbuildTree(self, edges: List[List[int]]) -> List[List[int]]: ans = [[] for _ inrange(len(edges) + 1)] for x, y in edges: ans[x].append(y) ans[y].append(x) return ans
defdfs(self, tree: List[List[int]], lastNode: int, thisNode: int, k: int) -> int: if k < 0: return0 ans = 1 for nextNode in tree[thisNode]: if nextNode != lastNode: ans += self.dfs(tree, thisNode, nextNode, k - 1) return ans
defmaxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]], k: int) -> List[int]: tree2 = self.buildTree(edges2) toAdd = max(self.dfs(tree2, -1, i, k - 1) for i inrange(len(tree2))) tree1 = self.buildTree(edges1) return [self.dfs(tree1, -1, i, k) + toAdd for i inrange(len(tree1))]
funcbuildTree3372(edges [][]int) [][]int { ans := make([][]int, len(edges) + 1) for _, edge := range edges { ans[edge[0]] = append(ans[edge[0]], edge[1]) ans[edge[1]] = append(ans[edge[1]], edge[0]) } return ans }
funcdfs3372(tree [][]int, lastNode, thisNode, k int)int { if k < 0 { return0 } ans := 1 for _, nextNode := range tree[thisNode] { if nextNode != lastNode { ans += dfs3372(tree, thisNode, nextNode, k - 1) } } return ans }
funcmaxTargetNodes(edges1 [][]int, edges2 [][]int, k int) []int { tree2 := buildTree3372(edges2) toAdd := 0 for i := range tree2 { toAdd = max(toAdd, dfs3372(tree2, -1, i, k - 1)) } tree1 := buildTree3372(edges1) ans := make([]int, len(tree1)) for i := range ans { ans[i] = toAdd + dfs3372(tree1, -1, i, k) } return ans }