题意：给出一棵树，带有向边，找出某个点到达所有点需要反转的最少的边。
解题关键：和求树的直径的思路差不多，将求（父树-子树）的最大值改为求特定值。依然是两次dfs，套路解法。
对树形dp的理解：树形dp其实就是将树进行暴力搜索，只是需要理解状态的概念。那些状态已经完成，需要从底还是从顶开始搜索。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<cmath> 6 #include<iostream> 7 using namespace std; 8 typedef long long ll; 9 const int maxn=1e6+3; 10 const int inf=0x3f3f3f3f; 11 int head[maxn],tot,n,m,sum; 12 int dp[maxn][3],cnt[maxn]; 13 struct edge{ 14 int to; 15 int nxt; 16 int w; 17 }e[maxn<<2]; 18 void add_edge(int u,int v,int w){ 19 e[tot].to=v; 20 e[tot].w=w; 21 e[tot].nxt=head[u]; 22 head[u]=tot++; 23 } 24 25 void dfs1(int u,int fa){ 26 for(int i=head[u];i!=-1;i=e[i].nxt){ 27 int v=e[i].to; 28 if(v==fa) continue; 29 dfs1(v,u); 30 dp[u][0]+=dp[v][0]+e[i].w; 31 } 32 } 33 34 void dfs2(int u,int fa){ 35 for(int i=head[u];i!=-1;i=e[i].nxt){ 36 int v=e[i].to; 37 if(v==fa) continue; 38 dp[v][1]=dp[u][0]-dp[v][0]+dp[u][1]; 39 if(e[i].w==0) dp[v][1]+=1; 40 else dp[v][1]-=1; 41 dfs2(v,u); 42 } 43 } 44 45 inline int read(){ 46 char k=0;char ls;ls=getchar();for(;ls<'0'||ls>'9';k=ls,ls=getchar()); 47 int x=0;for(;ls>='0'&&ls<='9';ls=getchar())x=(x<<3)+(x<<1)+ls-'0'; 48 if(k=='-')x=0-x;return x; 49 } 50 51 int main(){ 52 int k=0; 53 while(scanf("%d",&n)!=EOF){ 54 memset(head,-1,sizeof head); 55 tot=0; 56 int a,b; 57 /*for(int i=1;i<n;i++){ 58 cnt[i]=read(); 59 sum+=1ll*cnt[i]; 60 }*/ 61 for(int i=0;i<n-1;i++){ 62 a=read(); 63 b=read(); 64 add_edge(a,b,0); 65 add_edge(b,a,1); 66 } 67 dfs1(1,-1); 68 dfs2(1,-1); 69 for(int i=1;i<=n;i++){ 70 dp[i][2]=dp[i][0]+dp[i][1]; 71 } 72 int min1=inf; 73 for(int i=1;i<=n;i++){ 74 min1=min(dp[i][2],min1); 75 } 76 cout<<min1<<" "; 77 for(int i=1;i<=n;i++){ 78 // cout<<dp[i][2]<<" "; 79 if(dp[i][2]==min1) cout<<i<<" "; 80 } 81 } 82 return 0; 83 return 0; 84 }