analysis
树的重心的变式 重心：
对于一棵树n个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点数最小。换句话说，删除这个点后最大连通块（一定是树）的结点数最小。
其性质（重要性质证明见T3）：
树中所有点到某个点的距离和中，到重心的距离和是最小的把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。一棵树最多有两个重心，且相邻。
利用这些性质，我们可以对这个问题进行分析了： 借鉴带权中位数的思路（调整法），我们可以得到
树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样。
至少对于一个点权都为1的树是这样子的 知道了这一点后，我们不难发现，对于有点权的树也是一样，可以采用下面的方法来理解这一点
（转自luogu，侵删） 问题引入
问题转化
至此就完成了重心在本题的应用 （注：重心与边权无关，因为调整的时候增量和减量都可以提出同一个公因式：此条边的权值）
code
#include<bits/stdc++.h>
using namespace std
;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define ll long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
template<typename T
>void read(T
&x
){
x
=0;char r
=getchar();T neg
=1;
while(r
>'9'||r
<'0'){if(r
=='-')neg
=-1;r
=getchar();}
while(r
>='0'&&r
<='9'){x
=(x
<<1)+(x
<<3)+r
-'0';r
=getchar();}
x
*=neg
;
}
int n
,cnt
=0;
const int maxn
=100000+10;
struct node
{int _v
;int _w
;int nxt
;}edge
[maxn
<<1];
int head
[maxn
];
inline void addl(int u
,int v
,int w
){
edge
[cnt
]._v
=v
;
edge
[cnt
]._w
=w
;
edge
[cnt
].nxt
=head
[u
];
head
[u
]=cnt
++;
}
int c
[maxn
],f
[maxn
],maxs
[maxn
];
ll sum
=0;
void dfs(int u
,int fa
){
f
[u
]=c
[u
];
for(int i
=head
[u
];i
!=-1;i
=edge
[i
].nxt
){
int v
=edge
[i
]._v
;
if(v
==fa
)continue;
dfs(v
,u
);
f
[u
]+=f
[v
];
if(f
[v
]>maxs
[u
])maxs
[u
]=f
[v
];
}if(sum
-f
[u
]>maxs
[u
])maxs
[u
]=sum
-f
[u
];
}
int zx
;
int dis
[maxn
];
deque
<int>q
;
inline void spfa(){
clean(dis
,0x7f);
dis
[zx
]=0;
q
.push_back(zx
);
while(q
.empty()==false){
int f
=q
.front();q
.pop_front();
for(int i
=head
[f
];i
!=-1;i
=edge
[i
].nxt
){
int v
=edge
[i
]._v
;
if(dis
[v
]>dis
[f
]+edge
[i
]._w
){
dis
[v
]=dis
[f
]+edge
[i
]._w
;
if(q
.empty()==false&&dis
[v
]<dis
[q
.front()])q
.push_front(v
);
else q
.push_back(v
);
}
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("datain2.txt","r",stdin);
#endif
clean(head
,-1);
read(n
);clean(maxs
,0);
loop(i
,1,n
)read(c
[i
]),sum
+=c
[i
];
loop(i
,1,n
-1){
int xi
,yi
,li
;
read(xi
),read(yi
),read(li
);
addl(xi
,yi
,li
);addl(yi
,xi
,li
);
}dfs(1,0);
zx
=1;
loop(i
,2,n
)if(maxs
[zx
]>maxs
[i
])zx
=i
;
spfa();
ll res
=0;
loop(i
,1,n
){
res
=res
+(ll
)dis
[i
]*(ll
)c
[i
];
}printf("%lld\n",res
);
return 0;
}
