import sysclass Tree:def __init__(self, n):self.size = n + 1self.cur_size = 0self.tree = [[] for _ in range(self.size)]self.iscentroid = [False] * self.sizeself.ctree = [[] for _ in range(self.size)]self.characters=[None for _ in range(self.size)]def dfs(self, src, visited, subtree):visited[src] = Truesubtree[src] = 1self.cur_size += 1for adj in self.tree[src]:if not visited[adj] and not self.iscentroid[adj]:self.dfs(adj, visited, subtree)subtree[src] += subtree[adj]def findCentroid(self, src, visited, subtree):iscentroid = Truevisited[src] = Trueheavy_node = 0