Katty and Wonki
Time limit1sMemory limit256 MB
Add 2 edges to an N-vertex tree to maximize vertices lying on created cycles; return that maximum for the worst case for the tree owner.
Problem
Katty recently scammed Wonki. Wonki now wants revenge on Katty.
Katty has a tree with N vertices, which she treasures. The mischievous Wonki plans to add an edge connecting two vertices of the tree.
Wonki wanted to add as many edges as possible, but he fears the revenge of Katty, the tree's owner, so he will add just 2 edges.
Adding edges creates several cycles, and Wonki wants to ruin Katty's tree by maximizing the number of vertices that belong to those cycles.
Katty learns of the plan and wants to find out the worst case for her tree.
Find the maximum number of vertices that belong to the cycles created when Wonki adds 2 edges.
The graph that results after Wonki adds the two edges may contain duplicate edges or self loops.
A vertex that belongs to several cycles is counted exactly once, and a self loop counts as one cycle.
Input
The first line gives the number of vertices N of the tree. (1 ≤ N ≤ 105)
The following N-1 lines give the two vertex numbers joined by each edge of the tree, separated by a space.
Output
Print the maximum number of vertices that belong to the cycles after 2 edges are added.