<题目链接>
题目大意：
一颗无向树，现在问你最多能够删除多少条边，使得最终分成的多个节点块，每个节点块所含节点数为偶数。
解题分析：
可以想到，如果以某个节点为根的子树节点数为奇数(包括该节点本身)，那么肯定不会对该子树进行割边操作，因为割出的节点块必然存在奇数的情况。所以我们先进行DFS，计算出每个节点以自己为根的子树节点数，然后，因为要使割边最大，所以我们贪心地在树中，自下而上，遇到节点数为偶数的子树，就将其从树上割下，最后就能得到最大的割边数量。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define N int(1e5+7) 5 int cnt,ans,num[N],head[N]; 6 struct Edge{ 7 int to,nxt; 8 }edge[N<<1]; 9 10 template<typename T> 11 inline T read(T&x){ 12 x=0;int f=0;char ch=getchar(); 13 while(ch<‘0‘||ch>‘9‘)f|=(ch==‘-‘),ch=getchar(); 14 while(ch>=‘0‘ && ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar(); 15 return x=f?-x:x; 16 } 17 void addedge(int u,int v){ 18 edge[cnt].to=v,edge[cnt].nxt=head[u]; 19 head[u]=cnt++; 20 } 21 void dfs(int u,int fa){ 22 num[u]=1; 23 for(int i=head[u];~i;i=edge[i].nxt){ 24 int v=edge[i].to; 25 if(v==fa)continue; 26 dfs(v,u); 27 num[u]+=num[v]; 28 } 29 if(!(num[u]&1))num[u]=0,ans++; //将该偶数节点块从树上取下 30 } 31 int main(){ 32 int n;read(n); 33 cnt=0,ans=0;memset(head,-1,sizeof(head)); 34 for(int i=1;i<n;i++){ 35 int u,v;read(u);read(v); 36 addedge(u,v);addedge(v,u); 37 } 38 if(n&1)puts("-1"); //如果一开始n就为奇数，肯定不符合 39 else{ 40 dfs(1,-1); 41 ans--; //最后一个节点块不需要进行割边操作 42 printf("%d\n",ans); 43 } 44 }
2019-02-16
CodeForces 982C Cut 'em all 【DFS】+【贪心】
原文：https://www.cnblogs.com/00isok/p/10387288.html