[codeforces219D]Choosing Capital for Treeland树形dp

题意：给出一棵树，带有向边，找出某个点到达所有点需要反转的最少的边。

解题关键：和求树的直径的思路差不多，将求（父树-子树）的最大值改为求特定值。依然是两次dfs，套路解法。

对树形dp的理解：树形dp其实就是将树进行暴力搜索，只是需要理解状态的概念。那些状态已经完成，需要从底还是从顶开始搜索。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 const int maxn=1e6+;

 const int inf=0x3f3f3f3f;

 int head[maxn],tot,n,m,sum;

 int dp[maxn][],cnt[maxn];

 struct edge{

     int to;

     int nxt;

     int w;

 }e[maxn<<];

 void add_edge(int u,int v,int w){

     e[tot].to=v;

     e[tot].w=w;

     e[tot].nxt=head[u];

     head[u]=tot++;

 }

 void dfs1(int u,int fa){

     for(int i=head[u];i!=-;i=e[i].nxt){

         int v=e[i].to;

         if(v==fa) continue;

         dfs1(v,u);

         dp[u][]+=dp[v][]+e[i].w;

     }

 }

 void dfs2(int u,int fa){

     for(int i=head[u];i!=-;i=e[i].nxt){

         int v=e[i].to;

         if(v==fa) continue;

         dp[v][]=dp[u][]-dp[v][]+dp[u][];

         if(e[i].w==) dp[v][]+=;

         else dp[v][]-=;

         dfs2(v,u);

     }

 }

 inline int read(){

     char k=;char ls;ls=getchar();for(;ls<''||ls>'';k=ls,ls=getchar());

     int x=;for(;ls>=''&&ls<='';ls=getchar())x=(x<<)+(x<<)+ls-'';

     if(k=='-')x=-x;return x;

 }

 int main(){

     int k=;

     while(scanf("%d",&n)!=EOF){

         memset(head,-,sizeof head);

         tot=;

         int a,b;

         /*for(int i=1;i<n;i++){

             cnt[i]=read();

             sum+=1ll*cnt[i];

         }*/

         for(int i=;i<n-;i++){

             a=read();

             b=read();

             add_edge(a,b,);

             add_edge(b,a,);

         }

         dfs1(,-);

         dfs2(,-);

         for(int i=;i<=n;i++){

             dp[i][]=dp[i][]+dp[i][];

         }

         int min1=inf;

         for(int i=;i<=n;i++){

             min1=min(dp[i][],min1);

         }

         cout<<min1<<"\n";

         for(int i=;i<=n;i++){

         //    cout<<dp[i][2]<<" ";

             if(dp[i][]==min1) cout<<i<<" ";

         }

     }

     return ;

     return ;

 }