Tree Painting#11002
You are given a tree (an undirected connected acyclic graph) consisting of vertices. You are playing a game on this tree.
Initially, all vertices are colored white. On the first move, you choose one vertex and repaint it black. After that, on each move you choose a white vertex adjacent (i.e., connected by an edge) to at least one black vertex and repaint it black.
Each time you choose a vertex (including the first move), you gain a number of points equal to the size of the connected component consisting only of white vertices that contains the chosen vertex. The game ends when all vertices become black.
Consider the following example:
Vertices and are already colored black. If you choose vertex , you will gain points for the connected component consisting of vertices 2, 3, 5, and . If you choose vertex , you will gain points for the connected component consisting of vertices and .
Your task is to maximize the total number of points you can obtain.
The first line contains one integer n~(2 \le n \le 2 \cdot 10^5) — the number of vertices in the tree.
Each of the next n - 1 lines describes an edge of the tree. The -th edge is given by two integers u_i and v_i~(1 \le u_i, v_i \le n,\ u_i \ne v_i) — the indices of the vertices it connects.
It is guaranteed that the given edges form a tree.
Print one integer — the maximum number of points you can obtain when playing optimally.
Example 1
Example 2