Maximizing Message Passing in a Directed Tree

We are given a tree with n nodes numbered from 1 to n. Each node i has a weight a_i. The tree is undirected and its maximum degree is at most p (this constraint is guaranteed by the input). Originally, every edge represents a two‐way connection. However, the system is modified so that each edge is assigned a unique direction (i.e. for every undirected edge between u and v, exactly one of u → v or v → u is chosen).

The system defines that if there exists a directed path from node i to node j (passing over one or more directed edges; note that an edge is never traversed twice), then we say that i can reach j. We define the indicator function \[ [i\rightarrow j]=\begin{cases}1,&\text{if node }i\text{ can reach node }j,\\0,&\text{otherwise,}\end{cases} \] with the convention that \([i\rightarrow i]=0\).

The goal is to choose an orientation for every edge so that the following sum is maximized: \[ \sum_{i=1}^{n}\sum_{j=1}^{n}a_i\,a_j\,[i\rightarrow j]. \]

A key observation is that because the underlying graph is a tree, the unique undirected path between any two distinct nodes can be made into a directed path in exactly one of two ways. In fact, one optimal strategy is to choose a root r and orient every edge away from r. In the resulting directed tree (or arborescence), for any two nodes i and j, a directed path from i to j exists if and only if i is an ancestor of j.

If we fix a root r and let T(u) be the sum of weights in the subtree of node u (including u itself), then the contribution of node u (when u is an ancestor) is a_u (T(u) - a_u). Therefore the total sum for that rooting is given by: \[ \text{dp}(r)=\sum_{u\in tree}a_u\,(T(u)-a_u). \]

Your task is to compute the maximum possible sum over all valid orientations (equivalently, over all choices of a root r for the arborescence).

inputFormat

The first line contains two integers n and p — the number of nodes and the maximum degree of the tree, respectively.

The second line contains n integers \(a_1, a_2, \ldots, a_n\) representing the weights of the nodes.

Each of the next n − 1 lines contains two integers u and v, denoting an edge between nodes u and v.

outputFormat

Output a single integer — the maximum possible value of the sum \[ \sum_{i=1}^{n}\sum_{j=1}^{n}a_i\,a_j\,[i\rightarrow j], \] when the tree’s edges are assigned a direction as described.

sample

2 1
1 2
1 2

2