Largest Proper Subtree

Difficulty: 1500 4000 ms 128 MB

trees

Rooted at node 1, print the size (node count) of the largest subtree hanging below the root — i.e. the largest subtree of any non-root node.

Input: the first line has N (N ≥ 2); each of the next N−1 lines has an edge u v.

Output: the maximum subtree size among non-root nodes.

Constraints:

• 2 ≤ N ≤ 10⁵

Sample Tests

5
1 2
2 3
2 4
1 5

3

2
1 2

1

Read the Editorial