题目大意：
根据n个城市，设置n-1条有向边，希望设定一个中心城市，能通过修改一些道路的方向到达任何一座城市，希望修改的道路数量最少
输出这个最少的道路数量，并且把所有符合的可作为中心的城市编号一个个输出来
开始也实在想不出，根据树形dp，首先要确定一棵树，可是这里的边乱七八糟的，没法确定根
后来看了别人的思路，原来还是自己太死脑筋了，根本不需要确定根，可以把任意一个城市作为根来解决题目，这里假定1为根
把所有的有向边看作无向边，但要记录那条边是真实存在的，哪条是自己加的
用dp[i]表示 i 点到达其对应的子树中的所有点需要修改的边的数量
用一次dfs得到dp[i]
然后网上的大牛们都说2次dfs，后一次因为没写清楚，自己也不想看代码，就自己想了，可就是没办法写出dfs，最后发现直接就可以循环做。。。而且更好理解
做法：
len[i]记录 i 到 root 这里定义root为 1 长度，也就是i 到 1 之间有多少条边
change[i] 表示这 len[i]条边中有多少条改变了
这两个值可以在第一次dfs中实现
然后对于每一个点 i 来说，其实为了让 i 能够到达任何一点，只要改动 i 到 1 这len[i]条边即可，画个图很容易发现
1作为树根，i 到 1 的过程经过的都是一棵棵子树的根，能到达这些子树的根，必能到达子树中的任何一点，所以希望能够到达 1 即可
用rec[i]记录以 i 为中心城市需要改动的边
rec[i] = dp[1] - change[i] + (len[i] - change[i]) //减第一个change[i]是把原来改过的边改回来，然后+后面的是因为为了 i 到1，需要将那些
方向正常的 len[i] - change[i]倒转
最后通过rec[i]得到答案即可= =
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 const int N = 200005; 6 7 int first[N] , k , len[N] , change[N] , dp[N] , rec[N]; 8 9 struct Edge{ 10 int y , next; 11 bool flag; 12 }e[N<<1]; 13 14 void add_edge(int x , int y , bool flag) 15 { 16 e[k].y = y , e[k].next = first[x] , e[k].flag = flag; 17 first[x] = k++; 18 } 19 20 void dfs(int u , int fa) 21 { 22 for(int i = first[u] ; i!=-1 ; i=e[i].next){ 23 int v = e[i].y; 24 if(v == fa) continue; 25 len[v] = len[u]+1; 26 change[v] = change[u]; 27 if(!e[i].flag) change[v]++; 28 dfs(v , u); 29 if(!e[i].flag){ 30 dp[u] += dp[v]+1; 31 } 32 else{ 33 dp[u] += dp[v]; 34 } 35 } 36 } 37 38 int main() 39 { 40 // freopen("a.in" , "r" , stdin); 41 int n , a , b; 42 while(scanf("%d" , &n) == 1) 43 { 44 memset(first , -1 , sizeof(first)); 45 k = 0; 46 for(int i=1 ; i<n ; i++){ 47 scanf("%d%d" , &a , &b); 48 add_edge(a , b , true); 49 add_edge(b , a , false); 50 } 51 memset(dp , 0 , sizeof(dp)); 52 len[1] = 0 , change[1] = 0; 53 dfs(1 , -1); 54 55 int minn = 200000000; 56 57 for(int i=1 ; i<=n ; i++){ 58 rec[i] = dp[1] + len[i] - 2*change[i]; 59 // cout<<"i: "<<i<<" "<<len[i]<<" "<<change[i]<<" "<<rec[i]<<endl; 60 minn = min(minn , rec[i]); 61 } 62 printf("%d " , minn); 63 int num = 0; 64 for(int i=1 ; i<=n ; i++){ 65 if(minn == rec[i]){ 66 if(num == 0) printf("%d" , i); 67 else printf(" %d" , i); 68 num ++; 69 } 70 } 71 printf(" "); 72 } 73 return 0; 74 }