题解：P17275 [eJOI 2026] Teamfulness

lailai0916 · 2026-08-31 05:46:30 · 题解

题意简述

树上每个点有一种颜色。对每条直径，定义其价值为路径上的颜色数。求所有不同直径的价值之和。

解题思路

若直径长度为偶数，所有直径有同一个中心点；若直径长度为奇数，所有直径有同一条中心边。把奇数情形的中心边中间插入一个无色虚点后，两种情形可以统一处理。

先说明为什么中心对所有直径相同。 任选一条直径，并取出它的中心。 树上任意点到该中心的距离都不超过半径。 否则，这个点与原直径较远的端点之间会更长。

任意另一条直径的两个端点， 到中心的距离之和至少等于直径长度。 两段距离又都不超过半径。 所以它们必须同时取到半径， 且两端到中心的路径方向不同。 这就证明了共同中心的结论。

以中心为根。设半径为 h，把中心的每个儿子方向称为一个分支。分支 i 中距离中心为 h 的点都是直径端点，记其数量为 e_i。任取两个不同分支中的端点，就会得到一条直径。

固定一种颜色 c。记 q_{i,c} 为分支 i 中根链含有颜色 c 的端点数。已经处理的分支共有 E 个端点。其中有 Q_c 个端点的根链含有颜色 c。

加入新分支时，包含颜色 c 的新直径数为：

第一项要求旧端点的根链含有颜色 c。 新端点可以任意选择。

第二项要求旧端点的根链不含颜色 c。 此时，新端点的根链必须含有该颜色。

两种情况由旧端点是否含有该颜色划分。 所以，它们互不重复，也覆盖全部合法端点对。

下面计算一个分支内的所有 q_{i,c}。先求每个点子树中的直径端点数 s_u，再沿中心到端点的方向遍历。只在根链上第一次遇到颜色 a_u 时，把 s_u 加入 q_{i,a_u}。

对固定颜色观察这些首次出现的节点。 它们之间不存在祖先关系。 否则，较低节点就不是根链上的首次出现。

因此，这些节点的端点子树两两不交。 任意根链含有该颜色的端点， 又恰好属于其中最高同色节点的子树。 所以，所有 s_u 之和恰好等于 q_{i,c}。

每个点只会在所属分支中访问常数次。另维护 A=\sum_cQ_c，公式第一项对所有颜色之和就是 e_iA。第二项只涉及本分支实际出现的颜色。故更新时不必枚举全部颜色。

代码中的 sum_c 对应已经处理分支的 Q_c。