题解

思路

固定一种边权 $c$。删除所有权值为 $c$ 的边后，树被分成若干连通块。一条路径上权值 $c$ 恰好出现一次，当且仅当它的两个端点位于某条被删除边直接连接的两个连通块中。因此，这种颜色的贡献是每条 $c$ 边两侧相邻连通块大小的乘积之和。

做法

子任务一

当 $n\le11$ 时，枚举全部顶点对，恢复唯一路径并统计路径上每种权值的出现次数。复杂度为 $O(n^3)$。

子任务二

枚举每种实际出现的权值。对当前权值，忽略这种权值的边，用深度优先搜索求出删除后的全部连通块，再累加每条被删边两端连通块大小的乘积。复杂度为 $O(nk)$，其中 $k$ 是不同权值数量；在 $n\le2000$ 时可以通过。

满分做法

把树根定为 1。对每条边，用它的较深端点代表这条边。固定权值 $c$，设这些代表点组成集合 $S_c$。

按 DFS 序排列 $S_c$，用栈找到每个点在 $S_c$ 中最近的祖先，得到一棵虚森林。对 $v\in S_c$，记

$$g_v=\operatorname{size}(v)-\sum_{w\text{ 是 }v\text{ 的虚森林儿子}}\operatorname{size}(w).$$

$g_v$ 正是删除所有 $c$ 边后，包含 $v$ 的连通块大小。虚森林根之外的剩余根连通块大小为

$$g_0=n-\sum_{v\text{ 是虚森林根}}\operatorname{size}(v).$$

若 $v$ 的虚森林父亲为 $p$，代表边的贡献为 $g_vg_p$；若 $v$ 是虚森林根，则贡献为 $g_vg_0$。

复杂度

所有颜色集合的总大小为 $n-1$，排序总复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。