import sys from collections import deque def main(): sys.setrecursionlimit(1 << 25) N = int(sys.stdin.readline()) edges = [[] for _ in range(N + 1)] for _ in range(N - 1): x, y = map(int, sys.stdin.readline().split()) edges[x].append(y) edges[y].append(x) # Compute depth of each node using BFS depth = [0] * (N + 1) visited = [False] * (N + 1) q = deque() q.append(1) visited[1] = True depth[1] = 0 max_depth = 0 while q: u = q.popleft() for v in edges[u]: if not visited[v]: visited[v] = True depth[v] = depth[u] + 1 max_depth = max(max_depth, depth[v]) q.append(v) # Count the number of nodes at each depth depth_count = [0] * (max_depth + 1) for d in depth[1:]: # depth[0] is for node 1, which is root depth_count[d] += 1 # Compute count_ge[d] = number of nodes with depth >= d count_ge = [0] * (max_depth + 1) count_ge[max_depth] = depth_count[max_depth] for d in range(max_depth - 1, -1, -1): count_ge[d] = depth_count[d] + count_ge[d + 1] # Compute assign_count assign_count = [0] * (max_depth + 1) sum_assigned = 0 for d in range(max_depth, -1, -1): available = count_ge[d] - sum_assigned cap = 1 << d # 2^d assign = min(cap, available) assign_count[d] = assign sum_assigned += assign print(sum_assigned) if __name__ == "__main__": main()