POJ 4045 Power Station

// 给你一颗树，求一个点，使树上所有点到该点的距离之和最小。
//上次金华邀请赛的题目
//当时基本没接触过树形DP，连这么经典的都不会
//今天写了下、居然排第4,1A,唉、、、
//2次DFS，其中的道理在本子上划划就可以明白其中道理

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#define N 50005
using namespace std;
struct Edge
{
    int to,next;
}ed[N<<1];
__int64 sd[N];
int vc[N];
int node[N];
int rc[1000],p;
__int64 Min;
bool visit[N];
int n;
void dfs(int k)
{
    sd[k]=0;
    node[k]=1;
    visit[k]=1;
   int e,son;
   for(e=vc[k];;e=ed[e].next)
   {
       son=ed[e].to;
       if(!visit[son])
       {
           dfs(son);
           node[k]+=node[son];
           sd[k]+=sd[son]+node[son];
       }
       if(ed[e].next==-1) break;
   }
}
void Dfs(int k)
{
    visit[k]=1;
    int e,son;
    for(e=vc[k];;e=ed[e].next)
   {
       son=ed[e].to;
       if(!visit[son])
       {
           sd[son]=sd[k]+n-(node[son]<<1);
           if(sd[son]<Min)
           {
               Min=sd[son];
               rc[0]=son;
               p=1;
           }
           else if(sd[son]==Min)
           {
               rc[p++]=son;
           }
           Dfs(son);
       }
       if(ed[e].next==-1) break;
   }
}
int main()
{
    int T;
    int I,R;
    int i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&I,&R);
        int a,b;
        memset(vc,-1,sizeof(vc));
        memset(visit,0,sizeof(visit));
        for(j=i=1;i<n;i++)
        {
          scanf("%d%d",&a,&b);
          ed[j].to=b;
          ed[j].next=vc[a];
          vc[a]=j++;

          ed[j].to=a;
          ed[j].next=vc[b];
          vc[b]=j++;
        }
        dfs(1);
        Min=sd[1];
        p=1;rc[0]=1;
        memset(visit,0,sizeof(visit));
        Dfs(1);
        printf("%I64d\n",Min*I*I*R);
        sort(rc,rc+p);p--;
        for(i=0;i<p;i++)
          printf("%d ",rc[i]);
        printf("%d\n\n",rc[p]);
    }
    return 0;
}