题目理解

我们有一棵 $N$ 个节点的树，每个节点有一个颜色 $C_j$（表示特产）。对于每个节点 $x$，定义其"独特城市"为那些与 $x$ 的距离在整棵树中唯一的节点 $y$（即不存在其他节点 $z$ 与 $x$ 的距离等于 $dist(x,y)$）。

我们需要对每个节点 $x$，计算其所有独特城市所产特产的种类数。

关键观察

1. 独特城市的性质

对于树上的一个节点 $x$，其独特城市具有重要性质：

• 独特城市一定是 $x$ 的最远点之一，或者在某些深度上只有一个节点
• 更准确地说，对于每个深度 $d$，如果深度 $d$ 只有一个节点，那么这个节点就是独特的
• 如果某个深度有多个节点，那么这些节点都不是独特的

2. 树的直径与独特城市

重要定理：对于树中的任意节点 $x$，其独特城市一定位于树的某条直径的端点的路径上。

具体来说：

• 设树的直径端点为 $U$ 和 $V$
• 对于任意节点 $x$，其独特城市要么在 $x$ 到 $U$ 的路径上，要么在 $x$ 到 $V$ 的路径上

3. 深度分析

考虑以节点 $x$ 为根，设 $depth[y]$ 表示 $y$ 在根为 $x$ 的树中的深度。

节点 $y$ 是 $x$ 的独特城市当且仅当：

• 在深度 $depth[y]$ 上只有一个节点

换句话说，独特城市就是那些在深度分布中"独享"某个深度的节点。

算法设计

1. 整体思路

基于以上观察，我们可以设计以下算法：

1. 找到树的直径端点 $U$ 和 $V$
2. 分别以 $U$ 和 $V$ 为根，预处理整棵树
3. 对于每个节点 $x$，结合两个根下的信息计算答案

2. 具体步骤

步骤1：求直径

• 任选一个节点，通过 BFS/DFS 找到最远点 $U$
• 从 $U$ 出发，通过 BFS/DFS 找到最远点 $V$
• $U$ 和 $V$ 就是直径的两个端点

步骤2：预处理

以 $U$ 为根：

• 计算每个节点的深度 $depth_U$
• 记录每个深度的节点集合
• 记录每个节点的父节点信息

以 $V$ 为根：

• 同样计算 $depth_V$ 等信息

步骤3：计算答案

对于每个节点 $x$，其独特城市主要出现在两个方向：

1. 朝向 $U$ 的方向
2. 朝向 $V$ 的方向

我们需要统计这两个方向上，哪些深度是唯一的，然后计算这些深度上的节点的特产种类数。

3. 高效实现方法

方法1：深度计数

对于每个根 $R$，我们维护：

• $cnt[d][c]$：深度 $d$ 中颜色 $c$ 出现的次数
• $unique[d]$：深度 $d$ 中独特的颜色集合

当我们在树上移动时（如从父节点到子节点），深度分布会发生变化，需要动态维护这些信息。

方法2：重链维护

利用树链剖分的思想：

• 对树进行重链剖分
• 在每条重链上维护深度信息
• 通过重链快速更新和查询

4. 算法优化

关键优化：我们不需要对每个节点都重新计算所有信息，而是可以利用树的遍历顺序，在 DFS 过程中动态维护：

• 进入一个节点时，添加该节点对深度分布的影响
• 离开一个节点时，撤销该节点的影响
• 这样可以在 $O(1)$ 或 $O(\log n)$ 时间内更新状态

复杂度分析

• 求直径：$O(N)$
• 两次DFS预处理：$O(N)$
• 动态维护深度信息：使用合适的数据结构，每次更新 $O(\log N)$
• 总复杂度：$O(N \log N)$，对于 $N \leq 2\times 10^5$ 可以接受

特殊情况处理

Subtask 2: $M = 1$

所有城市产同一种特产，答案只能是 $0$ 或 $1$，大大简化。

Subtask 3: $M = N$ 且 $C_j = j$

每个城市的特产都不同，问题简化为统计独特城市的数量。

实现细节

1. 数据结构选择

• 使用 std::set 或 std::unordered_set 维护每个深度的节点颜色
• 使用数组记录每个深度的节点数量
• 使用栈或递归维护DFS状态

2. 信息维护

在DFS过程中：

• 进入节点 $x$ 时：
  • 将 $x$ 的颜色加入到当前深度的集合中
  • 更新深度计数
• 处理子树
• 离开节点 $x$ 时：
  • 从当前深度的集合中移除 $x$ 的颜色
  • 恢复深度计数

3. 答案计算

对于每个节点 $x$，其独特城市对应的颜色集合就是：

• 所有深度 $d$ 满足"该深度只有一个节点"的节点的颜色集合
• 取这些颜色的并集

总结

这道题的核心在于深入理解树的结构性质，特别是直径和深度分布在确定独特城市时的作用：

1. 结构分析：利用树的直径性质缩小候选范围
2. 深度唯一性：独特城市对应于深度分布中的唯一节点
3. 动态维护：通过DFS遍历动态更新深度信息
4. 高效计数：使用合适的数据结构快速计算颜色种类数

这种"结构性质 + 动态维护"的思路在解决树上的复杂计数问题时非常有效，是算法竞赛中的高级技巧。