http://codeforces.com/problemset/problem/219/D
题目大意：
给出一棵树，但是它的边是有向边，选择一个城市，问最少调整多少条边的方向能使一个选中城市可以到达所有的点，输出最小的调整的边数，和对应的点。
思路:先预处理一个点为根的代价，然后去dfs移动，总复杂度是O(n)
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #include<cstring> 5 #include<iostream> 6 int tot,go[400005],next[400005],first[200005],id[400005]; 7 int son[200005],f[200005],v[200005],n; 8 int read(){ 9 int t=0,f=1;char ch=getchar(); 10 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 11 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 12 return t*f; 13 } 14 void insert(int x,int y,int Id){ 15 tot++; 16 go[tot]=y; 17 next[tot]=first[x]; 18 first[x]=tot; 19 id[tot]=Id; 20 } 21 void add(int x,int y){ 22 insert(x,y,1);insert(y,x,-1); 23 } 24 void dfs(int x,int fa){ 25 son[x]=0; 26 for (int i=first[x];i;i=next[i]){ 27 int pur=go[i]; 28 if (pur==fa) continue; 29 if (id[i]==-1) v[pur]=1; 30 dfs(pur,x); 31 son[x]+=son[pur]+v[pur]; 32 } 33 } 34 void dp(int x,int fa){ 35 for (int i=first[x];i;i=next[i]){ 36 int pur=go[i]; 37 if (pur==fa) continue; 38 if (id[i]==1) f[pur]=f[x]+1; 39 else f[pur]=f[x]-1; 40 dp(pur,x); 41 } 42 } 43 int main(){ 44 n=read(); 45 for (int i=1;i<n;i++){ 46 int x=read(),y=read(); 47 add(x,y); 48 } 49 dfs(1,0); 50 f[1]=son[1]; 51 dp(1,0); 52 int ans=n; 53 for (int i=1;i<=n;i++) ans=std::min(ans,f[i]); 54 printf("%d ",ans); 55 for (int i=1;i<=n;i++) if (ans==f[i]) 56 printf("%d ",i); 57 return 0; 58 }