题目：http://acm.hdu.edu.cn/showproblem.php?pid=3899
题意：一棵树，给出每个点的权值和每条边的长度，点j到点i的代价为点j的权值乘以连接i和j的边的长度。求点x使得所有点到点x的代价最小，输出
非常恶心的题目我调试了N久，一直是WA。最后把long long改成了__int64一下就过了，在此鄙视下杭电的编译器
这道题要两次深搜。
1.求出每个节点作为根，他的下面节点到他的花费，以及数量。
2.求出每个节点的兄弟节点到他的花费以及数量。
3.求出每个节点除了他下面的节点的所有节点到他的花费和数量。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
//内存挂
const int maxn=100002;
int n,m,cnt[maxn],tn[maxn];///每个点的人数
__int64 dis[maxn];///最后要求结果
struct node
{
__int64 dis;
int v;
}tmp;
vector<node>p[maxn<<1];
void dfs(int u,int fa,__int64 len)
{
int i,j,v;
int sum=p[u].size();
dis[1]+=len*cnt[u];
tn[u]=cnt[u];
for(i=0;i<sum;i++)
{
int v=p[u][i].v;
if(v==fa)continue;
dfs(v,u,len+p[u][i].dis);
tn[u]+=tn[v];
}
}
void dfs1(int u,int fa)
{
int size=p[u].size();
for(int i=0;i<size;i++)
{
int v=p[u][i].v;
__int64 w=p[u][i].dis;
if(v==fa) continue;
dis[v]=dis[u]+(tn[1]-2*tn[v])*w;
///对于一条边，求出这条边上面所以边的长度和和下面所有边的长度和，然后就可以进行转移了
dfs1(v,u);
}
}
int main()
{
int u,v,i,j;
__int64 w;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%d",&cnt[i]);
dis[i]=0;
p[i].clear();
}
for(i=1;i<n;i++)
{
scanf("%d%d %I64d",&u,&v,&w);
tmp.v=v,tmp.dis=w;
p[u].push_back(tmp);
tmp.v=u,tmp.dis=w;
p[v].push_back(tmp);
}
dfs(1,-1,0);
__int64 ans=dis[1];
dfs1(1,0);
for(i=2;i<=n;i++)
{
if(ans>dis[i]) ans=dis[i];
}
printf("%I64d\n",ans);
}
return 0;
}
/*
3
1
1
2
1 2 2
2 3 1
4
100
1
1
1
1 2 1
2 3 1
2 4 1
*/