学步园

题意：给你一棵无向树，让你求以某个点为根，其他所有点到根节点的路径和最小，答案等于这个路径和*I*I*R，如果有多个路径和最小的点，输出所有的点。

1 这题题目只要输出T组，开始以为多case，以EOF结束，wa了几发。

2 注意答案可能超int，所有得用__int64或者long long 。

3 每组样例得输出一个空行。

dp[i]表示以i节点为根的路径和。

num[i]表示以i节点为根的节点数和。

dfs1()

dp[i]=dp[j]+num[j]; 

num[i]=sum(num[j])+1

dfs2()

dp[j]=dp[j]+(dp[i]-dp[j]-num[j])+(num[i]-num[j]);  画图理解下，其实就是通过父节点求子节点路径和。

代码：

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<cstdio>
#include<cstring>
#define maxn 50005
#define INF 0x1fffffffffffffff
#define ll long long
using namespace std;
int cnt,N;
int head[maxn],vis[maxn];
ll dp[maxn],num[maxn];
vector<int> g;
struct e
{
    int to,next;
} edg[maxn*2];
void init()
{
    cnt=0;
    memset(head,-1,sizeof(head));
    memset(dp,0,sizeof(dp));
    memset(num,0,sizeof(dp));
    memset(vis,0,sizeof(vis));
    g.clear();
}
void add(int from,int to)
{
    edg[cnt].to=to;
    edg[cnt].next=head[from];
    head[from]=cnt++;
}
void dfs1(int u)//求出以任意点为根的dp[],num[]
{
    vis[u]=1;
    num[u]=1;
    dp[u]=0;
    int v;
    for(int i=head[u]; i!=-1; i=edg[i].next)
    {
        v=edg[i].to;
        if(vis[v]==0)
        {
            dfs1(v);
            num[u]+=num[v];
            dp[u]+=(dp[v]+num[v]);
        }
    }
}
void dfs2(int u)
{
    vis[u]=1;
    int i,v;
    for(i=head[u]; i!=-1; i=edg[i].next)
    {
        v=edg[i].to;
        if(vis[v]==0)
        {
            dp[v]=dp[u]+N-2*num[v];
            dfs2(v);
        }
    }
}
int main()
{
    int t,I,R,i,j,k,a,b;
    scanf("%d",&t);

    while(t--)
    {
        init();
        scanf("%d%d%d",&N,&I,&R);
        for(i=1; i<N; i++)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        //num[i]记录以i为子树根节点的节点数,dp[i]记录以i为组数根节点到其他所有点的路径之和
        //vector<>记录所有最大值的点
        dfs1(1);
        for(i=1; i<=N; i++)
        {
            if(dp[i]<result)
            {
                g.clear();
                g.push_back(i);
                result =dp[i];
            }
            else if(dp[i]==result)
            {
                g.push_back(i);
            }
        }
        printf("%lld\n",result*I*I*R);
        int size=g.size();
        for(i=0; i<size; i++)
        {
            printf("%d",g[i]);
            printf("%c",i==size-1?'\n':' ');
        }
        printf("\n");
    }
    return 0;
}