解题思路

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

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

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

题目内容

某公司内有 $n$ 个部门，由 $n-1$ 条直接通讯线路连接，形成一个连通且无环的网络。部门 $1$ 为总部，整个网络构成以 $1$ 为根的层级结构。

对一个部门 $u$ ，定义其管辖范围 $S(u)$ 为 $u$ 及其所有直接或间接下属部门构成的集合。两个部门之间的级差定义为它们之间简单路径上的边数。

现有 $m$ 次查询，每次查询给出一个部门编号 $u$ ，请你计算 $S(u)$ 中所有无序部门对 $(v,w)$ （ $v<w$ ）的级差之和，即

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

其中 $\operatorname{diff}(v, w)$ 表示部门 $v$ 与 $w$ 的级差。