给出一个树，若去掉其中一个结点，剩下的子树中规模最大的树的规模（估且称为D值），就是该点的D值。求所有结点中D值最小的点，输出点及其D值。

这题用两次DFS，第一次求出所有结点的子结点数，第二次求出所有结点的D值。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define N 20005 5 using namespace std; 6 vector
        
          ed[N]; 7 int s[N],w[N],n; 8 int max(int a,int b) 9 {10     return a>b ?a :b ;11 }12 int dfs(int u, int fa)13 {14     int i;15     s[u] = 1;16     for(i = 0; i < ed[u].size(); i++)17     if(ed[u][i] != fa)18         s[u] += dfs(ed[u][i],u);19     //printf("s[%d]:%d\n",u,s[u]);20     return s[u];21 }22 void cal(int u, int fa)23 {24     int &ans = w[u],i,v,t=n-1;25     ans = 0;26     for(i = 0; i < ed[u].size(); i++)27     if(ed[u][i] != fa)28     {29         v = ed[u][i];30         cal(v,u);31         t -= s[v];32         if(s[v] > ans) ans = s[v];33     }34     ans = max(t,ans);35     //printf("f(%d):%d\n",u,ans);36 }37 int main()38 {39     int T,a,b,i,min,f;40     scanf("%d",&T);41     while(T--)42     {43         scanf("%d",&n);44         min = n;45         for(i = 1; i <= n; i++) ed[i].clear();46         for(i = 1; i < n; i++)47         {48             scanf("%d%d",&a,&b);49             ed[a].push_back(b);50             ed[b].push_back(a);51         }52         dfs(1,0);53         cal(1,0);54         for(i = 1; i <= n; i++)55         if(w[i] < min)56         {57             min = w[i];58             f = i;59         }60         printf("%d %d\n",f,min);61     }62     return 0;63 }