题目链接：

思路：其实就是求树的分支数，然后就是分支数*2+1(要删边，加边变成直线最后在成环)。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define MAXN 1000100 8 #pragma comment(linker, "/STACK:1024000000,1024000000") 9 10 int n,ans;11 vector
           
            
              >G;12 13 int dfs(int u,int father)14 {15 int tmp=0; //计算分支数，大于等于2时有分支。16 for(int i=0;i
             
              =2){22 if(u==1){ //如果是根节点的话，那么其有两条边在同一分支上。23 ans+=tmp-2;24 }else 25 ans+=tmp-1;//否则就是只能选择一条边在一个分支上26 return 0;27 }else 28 return 1;29 }30 31 int main()32 {33 int _case,u,v;34 scanf("%d",&_case);35 while(_case--){36 scanf("%d",&n);37 G.clear();38 G.resize(n+2);39 for(int i=1;i