### 问题描述 小乐给你一棵 $n$ 个节点的有根树（$1$ 号节点为根），每个节点都有一个权值 $w_i$，他定义了如下值： - $d(u,v)$：表示 $u$ 和 $v$ 之间的距离。 - $f(u,v)$：表示 $u$ 到 $v$ 的这条路径上的所有点的权值之和。 - $g(u,v)$：表示从 $u$ 走到 $v$ 的代价，小乐每次从 $u$ 点出发走到 $v$，同时他有一次跳跃机会， 他可以直接跳到和 $u$ 到根节点路径上的任意一个点 $u'$，那么 $g(u,v)=d(u,u')^2+f(u',v)$。 他现在有 $Q$ 次询问，每次询问给出两个正整数 $u,v$，表示询问 $g(u,v)$ 的最小值。 ### 输入格式 第 $1$ 行输入两个正整数 $n,Q$，分别表示树的节点个数，以及询问次数。 第 $2$ 行输入 $n$ 个非负整数 $w_i$，表示每个点的点权。 接下来 $n -1$ 行，每行两个正整数 $u,v$，表示 $u$ 与 $v$ 之间有一条边。 接下来 $Q$ 行，每行两个正整数 $u,v$，表示询问 $g(u,v)$ 的最小值。 ### 输出格式 对于 $Q$ 次询问，每次询问都要在一行输出 $g(u,v)$ 的最小值。 ### 样例输入 ``` 6 2 1 2 3 4 5 6 1 2 1 3 2 4 2 5 3 6 1 4 4 6 ``` ### 样例输出 ``` 7 12 ``` ### 评测数据规模 对于所有评测数据，$1\leq n,Q\leq10^5$，$0\leq w_i\leq10^4$，且保证 $\sum w\leq10^4$，$1\leq u,v\leq n$。