解题思路

给定一棵以 1 为根的树。对任意节点 $u$，记其子树为 $S(u)$。每次询问要计算

其中 $\operatorname{dist}$ 为树上最短路径边数。

题目内容

给定一棵节点数为 $n$ 的，树的根节点为 $1$ 。

对树中的任意节点 $u$ ，定义其子树为以为根的所有节点集合，记为 $S(u)$ 。

现有 $m$ 次查询，每次查询给定一个节点 $u$ ，请你计算子树 $S(u)$ 中所有节点对 $(v,w)$ 之间的距离和，

$\sum_{v, w \in S(u), v<w} \operatorname{dist}(v, w),$

其中 $dist(v,w)$ 表示节点 $v$ 与 $w$ 之间的距离。

【名词解释】

• 树:树是一种连接无环的无向图。

• 子树:子树指给定节点及其所有后代节点组成的连通子图。

• 距离:距离表示树中两节点之间的边数最短路径长度。

输入描述

第一行输入两个整数 $n$ 和 $m(1≦n,m≦2×10^5)$，分别表示树的节点数量与查询次数。

接下来 $n-1$ 行，每行输入两个整数 $u_i,v_i(1≦u_i,v_i≦n;u_i≠v_i)$，表示树的一条边。

接下来 $m$ 行，每行输入一个整数 $u(1≦u≦n)$ ，表示一次查询的节点编号。

输出描述

对于每次查询，在一行上输出一个整数，表示对应节点子树中所有节点对距离和。

样例1

输入

5 3
1 2
1 3
3 4
3 5
1
3
4

输出

18
4
0

说明

在这个样例中:

• 节点 $1$ 的子树为 {$1,2,3,4,5$}，其所有 $10$ 对距离之和为 $18$ ;

• 节点 $3$ 的子树为 {$3,4,5$}，距离和 $1+1+2=4$ ;

• 节点 $4$ 的子树仅为自身，贡献距离和 $0$ .

样例2

输入

3 2
1 2
2 3
2
3

输出

1
0

说明

在这个样例中:

• 节点 $2$ 的子树为 {$2,3$}，距离和 $1$ ;
• 节点 $3$ 的子树为 {$3$}，距离和 $0$ .