ACdream 1031 Cut-白红宇

ACdream 1031 Cut

阅读量：5170 次

发布时间：2019-06-13

本文共 1034 字，大约阅读时间需要 3 分钟。

题意：给定一棵树，删除一些边，让整棵树被分成多个节点数为偶数的联通块，且联通块尽量多。

思路：如果出现连通且节点数为偶数的立即删除这个点与它父节点之间的边，尽量删除即可，因为题目说了保证n为偶数，删了偶数，剩下的还是偶数。

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10#define inf 0x3f3f3f3f#define PI pair
                 
                   typedef long long LL;const int maxn = 1e5 + 5;vector
                  
                   G[maxn];int ans;int dfs(int u, int pre) { int cnt = 0; for(int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; if(v == pre) continue; int w = dfs(v, u); if(w & 1) cnt++; else ans++; } return cnt+1;}int main() { int n; while(scanf("%d", &n) == 1) { for(int i = 1; i <= n; ++i) G[i].clear(); int u, v; for(int i = 0; i < n-1; ++i) { scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } ans = 0; dfs(1, -1); printf("%d\n", ans); } return 0;}