题意翻译

$\text{Bessie}$ 正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。

奶牛分布在 $n$ 个农场中的一个，这些农场由 $n - 1$ 条道路连接，并且从任意一个农场都能够到达另外一个农场。

道路$i$连接农场 $a_i$ 和 $b_i$。长度为 $len_i$。集会可以在 $n$ 个农场中的任意一个举行。每个牛棚中居住着 $c_i$只奶牛。

在选择集会的地点的时候，$\text{Bessie}$ 希望最大化方便程度(也就是最小化不方便程度)。比如选择第 $x$ 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和。

请帮 $\text{Bessi}$ 找出最方便的地点来举行大集会。

输入格式

第一行：一个整数 $n$

第二到 $n + 1$ 行 , 第 $i+1$ 行有一个整数 $c_i$

第 $n+2$ 行到 $2n$ 行：第 $i+n+1$ 行为 3 个整数，$a_i$ , $b_i$ , $len_i$

输出格式

输出仅有一行，包含一个值，表示最小的不方便值。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围与约定

对于$100\%$的数据，保证$1 \leq n \leq 10^5$，$1 \leq c_i , len_i \leq 1000$

分析

比较经典的换根法模型。

题目中已经告诉我们，$m = n - 1$，很明显，这是一棵树。

考虑树形$dp$，设$f[i]$表示节点$i$的不方便值。

之后考虑单独的一个节点$p$。若选择该节点的一个子节点举办聚会，则在该子节点的子树中的点将少走一条边，而不在该子节点子树中的点将多走一条边。

而对于一个点，它要么在该子节点的子树中，要么不在。

因此，我们可以先进行一次$\text{dfs}$，处理出每个节点的子树大小和子树中每个节点到根的路径之和，之后进行$dp$，转移方程为

$f[to] = f[u] - (size[to] \times dis[i]) + (cnt - size[to]) \times dis[i]$

其中，$size[i]$表示以$i$为根的子树大小，$cnt$表示每个节点的权值之和，$dis[i]$表示$i$这条边的边权。

如果还有什么的话，就是开$\text{long long}$

剩下的细节见代码注释。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(a))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;

int n , m , node[M];

struct Edge{
    int to , last , dis;
}edge[M << 1];

int edge_num;
int head[M << 1];

void add_edge(int from , int to , int dis){
    edge[++ edge_num] = (Edge){to , head[from] , dis}; 
    head[from] = edge_num;
    edge[++ edge_num] = (Edge){from , head[to] , dis}; 
    head[to] = edge_num;
}

ll size[M << 1] , road[M << 1] , f[M << 1] , cnt;
//size[i] 表示以i为根的子树大小，road[i] 表示以i为根的子树每个节点到i的路径之和
//cnt 表示每个节点上的权值之和。

void dfs(int u , int fa){   //预处理子树大小和子树到其根节点的路径之和
    size[u] = node[u];
    PE(i , u){
        int to = edge[i].to;
        if(to == fa) continue;
        dfs(to , u);
        size[u] += size[to];
        road[u] += road[to] + size[to] * edge[i].dis; 
        //处理时需要乘上该点的权值（一个点上可能有多头牛）
    } 
}

void dp(int u , int fa){
    PE(i , u){
        int to = edge[i].to;
        if(to == fa) continue;
        f[to] = f[u] - (size[to] * edge[i].dis) + (cnt - size[to]) * edge[i].dis;
        dp(to , u);
    }
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    scanf("%d" , &n);
    rep(i , 1 , n){
        scanf("%d" , &node[i]);
        cnt += node[i];
    } 
    int u , v , d;
    rep(i , 1 , n - 1){
        scanf("%d%d%d" , &u , &v , &d);
        add_edge(u , v , d);    
    }
    dfs(1 , 0);
    f[1] = road[1];
    dp(1 , 0);
    ll ans = 0x3f3f3f3f3f3f3f3f;
    rep(i , 1 , n) ans = min(ans , f[i]);
    printf("%lld\n" , ans);

    return 0;
}