题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3899
题意：吉林大学有n个学院，有n-1条路保证这n个学院两两相连，现在要举行一场程序设计大赛，问在哪一个学院举行，所需的花费最少。
在第i个学院举行所需的花费为sum(dis（i，j）*num[j]) ,(1=<j <= n);
dis(i,j)表示第j个学院与第i个学院之间的距离,num[j]表示第j个学院有少个支队伍参赛！
由于n<=100000就限制了不能暴力枚举！
很明显的树形DP，先算出在第1个学院举行时所需的总花费。以第1个学院为根可以建一棵树，然后求出每个节点的Num值。
这个Num值包括该节点以及该节点的所有子孙节点的num值。
每个节点所需的总花费存在数组DP里面，那么DP[v]=DP[u]+(sum-Num[v])*edge[j].val+Num[v]*edge[j].val;
u是v的父亲节点，sum表示所有参赛队伍。
这样一深搜一光搜就ok了。
但是hdu存在爆栈的问题。。深搜需要手动模拟，很蛋疼。。结果写出来了虽然AC了，但跑了2000+ms；
看了别人的解题报告，发现可以预处理设置栈的内存大小，改了之后200ms+；
#pragma comment(linker, "/STACK:1024000000,1024000000")
预处理栈大小。后面的数字应该是可以根据具体的情况修改吧。
贴下手动模拟栈的吧：
# include<stdio.h>
# include<string.h>
# include<stack>
# include<queue>
# define N 100005
using namespace std;
int num[N];
struct node{int from,to,next,val;
}edge[2*N];
int head[N],tol,vis[N];
__int64 DP[N],Min,Num[N],sum,dis[N];
stack<int>S;
queue<int>S1;
void add(int a,int b,int c)
{edge[tol].from=a;edge[tol].to=b;edge[tol].val=c;edge[tol].next=head[a];head[a]=tol++;
}
void dfs()
{int j,v,u;S.push(1);while(!S.empty()){u=S.top();vis[u]=1;for(j=head[u];j!=-1;j=edge[j].next){v=edge[j].to;if(vis[v]) continue;dis[v]=dis[u]+edge[j].val;Min+=dis[v]*num[v];S.push(v);break;}if(j==-1){Num[u]=num[u];for(j=head[u];j!=-1;j=edge[j].next){v=edge[j].to;Num[u]+=Num[v];}S.pop();}}
}
/*void DFS()
{int j,v,u;S.push(1);while(!S.empty()){u=S.top();vis[u]=1;for(j=head[u];j!=-1;j=edge[j].next){v=edge[j].to;if(vis[v]) continue;DP[v]=DP[u]+(sum-Num[v]-Num[v])*edge[j].val;S.push(v);break;}if(j==-1) S.pop();}
}*/
void bfs()
{int j,u,v;S1.push(1);vis[1]=1;while(!S1.empty()){u=S1.front();S1.pop();for(j=head[u];j!=-1;j=edge[j].next){v=edge[j].to;if(vis[v]) continue;DP[v]=DP[u]+(sum-Num[v]*2)*edge[j].val;S1.push(v);vis[v]=1;}}
}
int main()
{int i,n,a,b,c;while(scanf("%d",&n)!=EOF){sum=0;for(i=1;i<=n;i++){scanf("%d",&num[i]);sum+=num[i];}tol=0;memset(head,-1,sizeof(head));for(i=1;i<n;i++){scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}Min=0;memset(vis,0,sizeof(vis));memset(Num,0,sizeof(Num));dis[1]=0;dfs();//先求出在college 1举办时所需的最少花费DP[1]=Min;memset(vis,0,sizeof(vis));bfs();for(i=1;i<=n;i++)if(DP[i]<Min) Min=DP[i];printf("%I64d\n",Min);}return 0;
}
