话说宁波市的中小学生在镇海中学参加计算机程序设计比赛，比赛之余，他们在镇海中学的各个景点参观。镇海中学共有n个景点，每个景点均有若干学生正在参 观。这n个景点以自然数1至n编号，每两个景点的编号均不同。每两个景点之间有且只有一条路径。选择哪个景点集中所有的学生，才能使所有学生走过的路径之和最小呢？
输入描述：
第一行只有一个正整数n，表示景点数。
第二行有n个1至1000间的整数，这n个整数间互相以一个空格分隔。其中第i个整数表示第i个景点处的学生数。
第三行至第n+1，每行有三个整数i,j,k，表示景点i和景点j之间有一条长为k的路径直接连接。其中i<>j，1≤i≤n, 1≤j≤n；1≤k≤1000。
输出描述：
有二行：
第一行只有一个整数i，表示在第i个景点处集中时，所有学生走过的路之和最短。
第二行也只有一个整数，表示所有学生走过的路径之和的最小值
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,num[],a,b,c,g[],tot,cnt,poi;//poi为最优点
long long ans[],minn=,siz[];//siz[i]以i为根节点的树的点权和，minn为最优答案，ans[i]为以i为根时的答案
struct s1
{int t,next;
long long l;
} e[];//e是边的相关信息，t是重点，next是下一条边，l是边权
void addedge(int s,int t,int l)//建图
{e[++tot].next=g[s];
g[s]=tot;
e[tot].t=t;
e[tot].l=l;
return;
}
void geta(int x,int d,int f)//预处理：随便找个点（这里是1）作为根节点遍历整棵树，计算以这个点为根时的siz和ans
{siz[x]=num[x];
for(int i=g[x];i!=;i=e[i].next)
if(e[i].t!=f)//因为最初是双向建边，所以这里应注意不需要重复处理。又因为树上没有环，所以别再去找父节点就行
{geta(e[i].t,d+e[i].l,x);
siz[x]+=siz[e[i].t];
ans[]+=siz[e[i].t]*e[i].l;
}
return;
}
void dp(int x,int f)
{if(ans[x]<minn)//到达每个点时ans必然是已经算好的，所以先更新minn和poi
{minn=ans[x];
poi=x;
}
for(int i=g[x];i!=;i=e[i].next)//计算好子节点的ans之后再将阶段转移到子节点，以继续计算其他的ans
if(e[i].t!=f)//同样不需要重复处理
{ans[e[i].t]=ans[x]+e[i].l*(cnt-*siz[e[i].t]);//由ans[e[i].t]=ans[x]+(cnt-siz[e[i].t])*e[i].l-siz[e[i].t]*e[i].l化简而来，即以e[i].t为根的子树上的点不需要再经过第i条边，其他点需要经过第i条边
dp(e[i].t,x);
}
return;
}
int main()
{freopen("p1487.in","r",stdin);
freopen("p1487.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;++i)
{scanf("%d",&num[i]);
cnt+=num[i];
}
for(int i=;i<n;++i)
{scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);//注意双向建边
addedge(b,a,c);
}
geta(,,);
dp(,);
cout<<poi<<endl<<minn<<endl;
return ;
}