CodeForces

http://codeforces.com/problemset/problem/219/D

题意：
给出有向五环图，现在要找一个点，使得它到其余所有点的需要逆转的边最少。即如果u—>v，那么v到u需要逆转边。

思路：

树形dp啦，需要逆转的边可以来自子树，也可以来自父亲结点。

分两次dfs即可，一次子树，一次父亲，熟悉的套路啊。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<sstream>
 6 #include<vector>
 7 #include<stack>
 8 #include<queue>
 9 #include<cmath>
10 #include<map>
11 #include<set>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,ll> pll;
15 const int INF = 0x3f3f3f3f;
16 const int maxn=2*1e5+5;
17 
18 int n;
19 int tot;
20 int head[maxn];
21 int d[maxn];
22 int r_d[maxn];
23 int ans;
24 
25 struct node
26 {
27     int to;
28     int next;
29     int flag;
30 }e[2*maxn];
31 
32 void addEdge(int u, int v, int x)
33 {
34     e[tot].to=v;
35     e[tot].flag=x;
36     e[tot].next=head[u];
37     head[u]=tot++;
38 }
39 
40 void dfs(int u, int fa)  //子树方向
41 {
42     d[u]=0;
43     for(int i=head[u];i!=-1;i=e[i].next)
44     {
45         int v=e[i].to;
46         if(v==fa)  continue;
47         dfs(v,u);
48         d[u]+=d[v]+e[i].flag;
49     }
50 }
51 
52 void dfs2(int u, int fa)  //父亲方向
53 {
54     for(int i=head[u];i!=-1;i=e[i].next)
55     {
56         int v=e[i].to;
57         if(v==fa)  continue;
58         r_d[v]=r_d[u]+d[u]-d[v]+(e[i].flag?0:1)-e[i].flag;
59         dfs2(v,u);
60     }
61 }
62 
63 int main()
64 {
65     //freopen("in.txt","r",stdin);
66     while(~scanf("%d",&n))
67     {
68         tot=0;
69         memset(head,-1,sizeof(head));
70         for(int i=1;i<n;i++)
71         {
72             int u,v;
73             scanf("%d%d",&u,&v);
74             addEdge(u,v,0);
75             addEdge(v,u,1);
76         }
77         ans=INF;
78         dfs(1,-1);
79         dfs2(1,-1);
80 
81         for(int i=1;i<=n;i++)  ans=min(ans,d[i]+r_d[i]);
82 
83         printf("%d
",ans);
84 
85         bool first=true;
86         for(int i=1;i<=n;i++)
87         {
88             if(d[i]+r_d[i]==ans)
89             {
90                 if(first)  {first=false;}
91                 else printf(" ");
92                 printf("%d",i);
93             }
94         }
95     }
96     return 0;
97 }