Let unsigned long long total_cost=0. For every edge E in tree total_cost +=cost_of_all_paths_lies_on_edge(E). double ans=2.0*total_cost/n/(n-1) is overflow and and WA#19. ================ Let double ans = 0. For every edge E in tree ans+=2.0*cost_of_all_paths_lies_on_edge(E)/n/(n-1). That is AC. =========== Maybe if not multiply by two in the first scenario there is also AC, I have not tested.