Great Cow Gathering G

Problem Statement

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

每个奶牛居住在 $N$ 个农场中的一个，这些农场由 $N-1$ 条道路连接，并且从任意一个农场都能够到达另外一个农场。道路 $i$ 连接农场 $A_i$ 和 $B_i$，长度为 $L_i$。集会可以在 $N$ 个农场中的任意一个举行。另外，每个牛棚中居住着 $C_i$ 只奶牛。

在选择集会的地点的时候，Bessie 希望最大化方便的程度（也就是最小化不方便程度）。比如选择第 $X$ 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和（比如，农场 $i$ 到达农场 $X$ 的距离是 $20$，那么总路程就是 $C_i\times 20$）。帮助 Bessie 找出最方便的地点来举行大集会。

Input

第一行一个整数 $N$ 。

第二到 $N+1$ 行：第 $i+1$ 行有一个整数 $C_i$。

第 $N+2$ 行到 $2N$ 行：第 $i+N+1$ 行为 $3$ 个整数：$A_i,B_i$ 和 $L_i$。

Ouput

一行一个整数，表示最小的不方便值。

Sample Input

Sample Output

1

15

Constraints

$1\leq N\leq 10^5$，$1\leq A_i\leq B_i\leq N$，$0 \leq C_i,L_i \leq 10^3$

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77


struct node
{
    int to,next,w;
};
void solve()
{
    int n;
    cin >> n;
    int cnt = 0;
    vector<int> head(n+1,0);
    vector<int> size(n+1);
    vector<int> C(n+1);
    vector<node> edge(n<<1);
    int sum = 0;
    for(int i=1;i<=n;i++) cin >> C[i],sum += C[i];
    int center;
    int best = INF;
    auto add = [&](int u,int v,int w) -> void
    {
        edge[++cnt].to = v;
        edge[cnt].w = w;
        edge[cnt].next = head[u];
        head[u] = cnt;
    };
    for(int i=1;i<=n-1;i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        add(u,v,w);
        add(v,u,w);
    }
    auto dfs = [&](auto &&self,int u,int fa) -> void
    {   
        size[u] = C[u]; // 找到以牛的数量为子树建树后树的重心
        int maxsub = 0;
        for(int i=head[u];i;i=edge[i].next)
        {  
            int v = edge[i].to;
            if(v != fa)
            {
                self(self,v,u);
                size[u] += size[v];
                maxsub = max(maxsub,size[v]);
            }
        }
        maxsub = max(maxsub,sum-size[u]);
        if(maxsub <= best)
        {
            best = maxsub;
            center = u;
        }
    };
    dfs(dfs,1,-1);
    // 求出汇集点 Center
    vector<int> dis(n+1,0); // dis[i] 表示 i 点到center的距离
    dis[center] = 0;
    auto dfs1 = [&](auto &&self,int u,int fa) -> void
    {           
        for(int i=head[u];i;i=edge[i].next)
        {
            int v = edge[i].to;
            int w = edge[i].w;
            if(v != fa)
            {     
                dis[v] = dis[u] + w;
                self(self,v,u);
            }
        }
    };
    dfs1(dfs1,center,-1);
    int ans1 = 0;
    for(int i=1;i<=n;i++)
    {
        ans1 += C[i] * dis[i];
    }
    cout << ans1 << endl;
}