Tree Coloring

Time limit2sMemory limit256 MB

Summary
Given a tree, assign colors 1 to n to vertices so adjacent vertices differ, minimizing the total cost equal to the sum of color numbers used.
Level

Medium6 of 10

Topics
Tree, BFS, Greedy, Math
Solved
No attempts yet

Problem

You are given a tree with n vertices. Each vertex must be colored with one of the colors numbered from 1 to n. Coloring one vertex with color i costs i.

Any two vertices directly connected by an edge must have different colors. Find the minimum possible total cost to color every vertex while satisfying this condition.

Input

The first line contains n, the number of vertices and also the number of available colors. (1 ≤ n ≤ 100,000)

Each of the next n - 1 lines contains two vertices u and v that are connected by an edge in the tree.

Output

Print the minimum total cost needed to color all vertices validly.

Examples1

  1. Example 1

    Input
    8
1 2
3 1
1 4
5 6
1 5
5 7
5 8
    Expected output
    11