题意：一条有向树，选择一个节点为根的话需要把朝向它的所有边都反转 ，问你最少需要反转几条边，选择那几个为根。
解题思路：树形DP，先统计从下而上，然后再自上而下。
解题代码：
1 // File Name: 219d.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月10日 星期二 19时26分38秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define maxn 200006 26 using namespace std; 27 map <int,int> mp[maxn]; 28 vector<int> dmp[maxn]; 29 int n ; 30 int dpx[maxn]; 31 int dfs(int k ,int la ) 32 { 33 for(int i = 0 ;i < dmp[k].size();i ++) 34 { 35 if(dmp[k][i] == la) 36 continue; 37 if(mp[k][dmp[k][i]] == 0) 38 dpx[k] ++ ; 39 dpx[k] += dfs(dmp[k][i],k); 40 } 41 return dpx[k]; 42 43 } 44 void dfs2(int k ,int s,int la) 45 { 46 dpx[k] += s; 47 for(int i = 0 ;i < dmp[k].size() ;i ++) 48 { 49 if(dmp[k][i] == la) 50 continue; 51 int tmp = dpx[k] - dpx[dmp[k][i]]; 52 if(mp[k][dmp[k][i]] == 1) 53 tmp ++ ; 54 else tmp -- ; 55 dfs2(dmp[k][i],tmp,k) ; 56 } 57 } 58 int main(){ 59 scanf("%d",&n); 60 memset(dpx,0,sizeof(dpx)); 61 for(int i = 1 ;i < n;i ++) 62 { 63 int ta, tb; 64 scanf("%d %d",&ta,&tb); 65 dmp[ta].push_back(tb); 66 dmp[tb].push_back(ta); 67 mp[ta][tb] = 1; 68 } 69 dfs(1,0); 70 dfs2(1,0,0); 71 int mi = 1e9 ; 72 for(int i = 1;i <= n;i ++) 73 { 74 mi = min(mi,dpx[i]); 75 //printf("%d ",dpx[i]); 76 } 77 printf("%d ",mi); 78 for(int i = 1;i <= n;i ++) 79 if(dpx[i] == mi) 80 printf("%d ",i); 81 return 0; 82 }