5719. D-攻占巨人国
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 攻占巨人国是一款战略游戏。 巨人国有n个城市，编号1到n，有n-1条道路，每条道路连接两个城市，且任意一对城市直接或间接相连。 开始，n座城池均未被攻占。第一回合，你可以选择攻打任意一个城市。接下来的每个回合，你只能攻打与占领的城市直接连接的未被攻占的城市，直到你攻占了所有城市。（ps:认为我方军事实力非常强，只要攻打就能占领） 每次攻占城市都可以获得战略分，战略分是被攻打城市所在的由未被攻占城市组成的连通块大小。 求最大可以获得多少战略分。 ## 输入格式 第一行，一个整数n，代表n个城市。 接下来n-1行，每一行两个整数u,v，代表u,v城市相连。 ## 输出格式 一个整数，代表**最大战略分**。 ## 输入 ```in1 9 1 2 2 3 2 5 2 6 1 4 4 9 9 7 9 8 ``` ## 输出 ```out1 36 ``` ```in2 5 1 2 1 3 2 4 2 5 ``` ```out2 14 ``` ## 提示 1-6测试点：n\le10^3 7-12测试点：n\le2\cdot10^4 13-18测试点：n\le2\cdot10^5 19测试点：n\le2\cdot10^5 （长链） 20测试点：n\le2\cdot10^5 （菊花图） PS：无特殊说明时，数据为随机数据